A heuristic block coordinate descent approach for controlled tabular adjustment

One of the main concerns of national statistical agencies (NSAs) is to publish tabular data. NSAs have to guarantee that no private information from specific respondents can be disclosed from the released tables. The purpose of the statistical disclosure control field is to avoid such a leak of private information. Most protection techniques for tabular data rely on the formulation of a large mathematical programming problem, whose solution is computationally expensive even for tables of moderate size. One of the emerging techniques in this field is controlled tabular adjustment (CTA). Although CTA is more efficient than other protection methods, the resulting mixed integer linear problems (MILP) are still challenging. In this work a heuristic approach based on block coordinate descent decomposition is designed and applied to large hierarchical and general CTA instances. This approach is compared with CPLEX, a state-of-the-art MILP solver. Our results, from both synthetic and real tables with up to 1,200,000 cells, 100,000 of them being sensitive (resulting in MILP instances of up to 2,400,000 continuous variables, 100,000 binary variables, and 475,000 constraints) show that the heuristic block coordinate descent has a better practical behavior than a state-of-the-art solver: for large hierarchical instances it provides significantly better solutions within a specified realistic time limit, as required by NSAs in real-world.     

A linear optimization-based method for data privacy in statistical tabular data

National Statistical Agencies routinely disseminate large amount of data. Prior to dissemination these data have to be protected to avoid releasing confidential information. Controlled tabular adjustment (CTA) is one of the available methods for this purpose. CTA formulates an optimization problem that looks for the safe table which is closest to the original one. The standard CTA approach results in a mixed integer linear optimization (MILO) problem, which is very challenging for current technology. In this work we present a much less costly variant of CTA that formulates a multiobjective linear optimization (LO) problem, where binary variables are pre-fixed, and the resulting continuous problem is solved by lexicographic optimization. Extensive computational results are reported using both commercial (CPLEX and XPRESS) and open source (Clp) solvers, with either simplex or interior-point methods, on a set of real instances. Most instances were successfully solved with the LO-CTA variant in less than one hour, while many of them are computationally very expensive with the MILO-CTA formulation. The interior-point method outperformed simplex in this particular application.     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

A set partitioning reformulation of a school bus scheduling problem

We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single-depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non-zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real-world instance are given and compared with results from a standard branch-and-cut approach.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

An improved genetic heuristic to support the design of flexible manufacturing systems

In industry, when flexible manufacturing systems are designed within a group technology approach, numerous decision-taking processes emerge requiring control of the multiple characteristics of the system. In this context, several grouping problems are identified within the scope of combinatorial optimisation. Such is the case of the part families with precedence constraints problem, which is defined in order to set up families where the total dissimilarity among the parts placed in the same family is minimal and precedence constraints, as well as capacity constraints arise when grouping parts. The present paper describes the use of an improved genetic heuristic to tackle this problem. It comprises a standard genetic heuristic with appropriate operators, improved through specific local search. In order to study the performance of the improved genetic approach, a special purpose constructive heuristic plus an earlier version of the genetic heuristic were implemented. CPLEX software was used from a binary linear formulation for this problem. Computational results are given from the experiment performed using test instances partly taken from the literature while others were semi-randomly generated. The improved genetic heuristic produced optimal solutions for most of the shortest dimension test instances and acted positively in relation to the constructive heuristic results, over almost all the instances. As for the CPLEX it found optimal solutions only for the small instances, besides which for the higher dimensioned instances CPLEX failed to obtain any integer solutions at all, in 10h running time. Therefore, these experiments demonstrate that the improved genetic is a good tool to tackle high dimensioned test instances, when one does not expect an exact method to find an optimal solution in reasonable computing time.     

Dantzig–Wolfe and block coordinate-descent decomposition in large-scale integrated refinery-planning

The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall planning problem, this work presents a mathematical model of the refinery operations characterized by complete horizontal integration of subsystems from crude oil purchase through to product distribution. This is the main contribution from a modelling point of view. The IRP, with a planning horizon ranging from 2 to 300 days, results in a large-scale linear programming (LP) problem of up to one million constraints, 2.5 million variables and 59 millions of nonzeroes in the constraint matrix. Large instances become computationally challenging for generic state-of-the-art LP solvers, such as CPLEX. To avoid this drawback, after the identification of the nonzero structure of the constraints matrix, structure-exploiting techniques such as Dantzig–Wolfe and block coordinate-descent decomposition were applied to IRP. It was also observed that interior-point methods are far more efficient than simplex ones in large IRP instances. These were the main contributions from the optimization viewpoint. A set of realistic instances were dealt with generic algorithms and these two decomposition methods. In particular the block coordinate-descent heuristic, with a reverse order of the subsystems, appeared as a promising approach for very large integrated refinery problems, obtaining either the optimal or an approximate feasible solution in all the instances tested.     

Uplink scheduling for joint wireless orthogonal frequency and time division multiple access networks

In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary second-order conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and sub-carrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for non-real-time applications where sub-channel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.     

A computational study on the quadratic knapsack problem with multiple constraints

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved by standard branch-and-cut optimizers available via CPLEX. Our results show that the linear models perform well on small problem instances but for larger problems the quadratic model outperforms the linear models tested both in terms of solution quality and solution time by a wide margin. Moreover, our results demonstrate that QKP instances larger than those previously addressed in the literature as well as instances with multiple constraints can be successfully and efficiently solved by branch and cut methodologies.     

求解阻塞混流生产机器人制造单元调度问题的分支定界算法

针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明：工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。     

A branch-and-cut approach for the vehicle routing problem with loading constraints

In this paper we describe a branch-and-cut algorithm for the vehicle routing problem with unloading constraints. The problem is to determine a set of routes with minimum total cost, each route leaving a depot, such that all clients are visited exactly once. Each client has a demand, given by a set of items, that are initially stored in a depot. We consider the versions of the problem with two and tri dimensional parallelepiped items. For each route in a solution, we also need to construct a feasible packing for all the items of the clients in this route. As it would be too expensive to rearrange the vehicle cargo when removing the items of a client, it is important to perform this task without moving the other client items. Such packings are said to satisfy unloading constraints.In this paper we describe a branch-and-cut algorithm that uses several techniques to prune the branch-and-cut enumeration tree. The presented algorithm uses several packing routines with different algorithmic approaches, such as branch-and-bound, constraint programming and metaheuristics. The careful combination of these routines showed that the presented algorithm is competitive, and could obtain optimum solutions within significantly smaller computational times for most of the instances presented in the literature.     

A simulated annealing approach to the traveling tournament problem

Automating the scheduling of sport leagues has received considerable attention in recent years, as these applications involve significant revenues and generate challenging combinatorial optimization problems. This paper considers the traveling tournament problem (TTP) which abstracts the salient features of major league baseball (MLB) in the United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores both feasible and infeasible schedules, uses a large neighborhood with complex moves, and includes advanced techniques such as strategic oscillation and reheats to balance the exploration of the feasible and infeasible regions and to escape local minima at very low temperatures. TTSA matches the best-known solutions on the small instances of the TTP and produces significant improvements over previous approaches on the larger instances. Moreover, TTSA is shown to be robust, because its worst solution quality over 50 runs is always smaller or equal to the best-known solutions. A Preliminary version of this paper was presented at the CP'AI'OR'03 Workshop.     

Cyclic staff scheduling: optimization models for some real-life problems

In this work, we propose a general integer programming model to address the staff scheduling problem, flexible enough to be easily adapted to a wide-range of real-world problems. The model is applied with slight changes to two case studies: a glass plant and a continuous care unit, and also to a collection of benchmark instances available in the literature. The emphasis of our approach is on a novel formulation of sequence constraints and also on workload balance, which is tackled through cyclic scheduling. Models are solved using the CPLEX solver. Computational results indicate that optimal solutions can be achieved within a reasonable amount of time.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

A hybrid VNS approach for the short-term production planning and scheduling: A case study in the pulp and paper industry

Mathematical formulations for production planning are increasing complexity, in order to improve their realism. In short-term planning, the desirable level of detail is particularly high. Exact solvers fail to generate good quality solutions for those complex models on medium- and large-sized instances within feasible time. Motivated by a real-world case study in the pulp and paper industry, this paper provides an efficient solution method to tackle the short-term production planning and scheduling in an integrated mill. Decisions on the paper machine setup pattern and on the production rate of the pulp digester (which is constrained to a maximum variation) complicate the problem. The approach is built on top of a mixed integer programming (MIP) formulation derived from the multi-stage general lotsizing and scheduling problem. It combines a Variable Neighbourhood Search procedure which manages the setup-related variables, a specific heuristic to determine the digester's production speeds and an exact method to optimize the production and flow movement decisions. Different strategies are explored to speed-up the solution procedure and alternative variants of the algorithm are tested on instances based on real data from the case study. The algorithm is benchmarked against exact procedures.     

MaxSAT-based large neighborhood search for high school timetabling

High School Timetabling (HSTT) is a well known and wide spread problem. The problem consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. lectures) with respect to various constraints. Unfortunately, HSTT is hard to solve and just finding a feasible solution for simple variants of HSTT have been proven to be NP-complete. We propose a new algorithm for HSTT which combines local search with a novel maxSAT-based large neighborhood search. A local search algorithm is used to drive an initial solution into a local optimum and then more powerful large neighborhood search (LNS) techniques based on maxSAT are used to further improve the solution. We prove the effectiveness of our approach with experimental results on instances taken from the Third International Timetabling Competition 2011 and the XHSTT-2014 benchmark archive. We were able to model 27 out of 39 instances. The remaining 12 instances were not modeled because the currently used maxSAT formulation for XHSTT does not support resource assignments in general. For the instances which could be modeled, our algorithm shows good performance when compared to other XHSTT state-of-the-art solvers and for several instances new best known upper bounds have been computed.     

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

A comparison of five heuristics for the multiple depot vehicle scheduling problem

Given a set of timetabled tasks, the multi-depot vehicle scheduling problem consists of determining least-cost schedules for vehicles assigned to several depots such that each task is accomplished exactly once by a vehicle. In this paper, we propose to compare the performance of five different heuristics for this well-known problem, namely, a truncated branch-and-cut method, a Lagrangian heuristic, a truncated column generation method, a large neighborhood search heuristic using truncated column generation for neighborhood evaluation, and a tabu search heuristic. The first three methods are adaptations of existing methods, while the last two are new in the context of this problem. Computational results on randomly generated instances show that the column generation heuristic performs the best when enough computational time is available and stability is required, while the large neighborhood search method is the best alternative when looking for good quality solutions in relatively fast computational times.