Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching

The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

Minimum node covers and 2-bicritical graphs

The problem of finding a minimum cardinality set of nodes in a graph which meet every edge is of considerable theoretical as well as practical interest. Because of the difficulty of this problem, a linear relaxation of an integer programming model is sometimes used as a heuristic. In fact Nemhauser and Trotter showed that any variables which receive integer values in an optimal solution to the relaxation can retain the same values in an optimal solution to the integer program. We define 2-bicritical graphs and give several characterizations of them. One characterization is that they are precisely the graphs for which an optimal solution to the linear relaxation will have no integer valued variables. Then we show that almost all graphs are 2-bicritical and hence the linear relaxation almost never helps for large random graphs.This research was supported in part by the National Research Council of Canada.     

A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint

This paper studies a two-machine open shop scheduling problem with an availability constraint, ie we assume that a machine is not always available and that the processing of the interrupted job can be resumed when the machine becomes available again. We consider the makespan minimization as criterion. This problem is NP-hard. We develop a pseudo-polynomial time dynamic programming algorithm to solve the problem optimally when the machine is not available at time s>0. Then, we propose a mixed integer linear programming formulation, that allows to solve instances with up to 500 jobs optimally in less than 5?min with CPLEX solver. Finally, we show that any heuristic algorithm has a worst-case error bound of 1.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

Minimizing makespan in a two-machine flowshop scheduling with batching and release time

This paper studies two-machine flowshop scheduling with batching and release time, whose objective is to minimize the makespan. We formulate the scheduling problem as a mixed integer programming model and show that it is a strongly NP-hard problem. We derive a lower bound and develop dynamic programming-based heuristic algorithms to solve the scheduling problem. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can indeed find effective solutions for the scheduling problem.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

TRACS II: a hybrid IP/heuristic driver scheduling system for public transport

We discuss the driver scheduling problem in public transport and describe a combined integer linear programming/heuristic approach to its solution. The approach has been applied successfully in many operational and planning scenarios. Recent developments in the algorithms used allow the solution of very large bus and rail problems.     

Repulsive Assignment Problem

Standard assignment is the problem of obtaining a matching between two sets of respectively persons and positions so that each person is assigned exactly one position and each position receives exactly one person, while a linear decision maker utility function is maximized. We introduce a variant of the problem where the persons individual utilities are taken into account in a way that a feasible solution must satisfy not only the standard assignment constraints, but also an equilibrium constraint of the complementarity type, which we call repulsive. The equilibrium constraint can be, in turn, transformed into a typically large set of linear constraints. Our problem is NP-hard and it is a special case of the assignment problem with side constraints. We study an exact penalty function approach which motivates a heuristic algorithm. We provide computational experiments that show the usefulness of a heuristic mechanism inspired by the exact approach. The heuristics outperforms a state-of-the-art integer linear programming solver.     

A piecewise linearization for retail shelf space allocation problem and a local search heuristic

Retail shelf space allocation problem is well known in literature. In this paper, we make three contributions to retail shelf space allocation problem considering space elasticity (SSAPSE). First, we reformulate an existing nonlinear model for SSAPSE to an integer programming (IP) model using piecewise linearization. Second, we show that the linear programming relaxation of the proposed IP model produces tight upper bound. Third, we develop a heuristic that consistently produces near optimal solutions for randomly generated instances of problems with size (products, shelves) varying from (25, 5) to (200, 50) within a minute of CPU time.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.     

Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph Partitioning

Performance-driven physical layout design is becoming increasingly important for both high speed integrated circuits and printed circuit boards. This paper studies the problem of assigning wire segments into two layers so as to minimize the number of vias, while taking into account performance constraints such as layer preference and circuit timing. We show that using the Elmore delay model, three timing problems in synchronous digital circuits—the long path problem, the short path problem and the time skew problem—can be formulated as a set of linear inequalities. We use the model of signed hypergraph to represent two-layer routings and formulate the performance-driven optimum layer assignment problem as the path-constrained maximum balance problem in a signed hypergraph. Two solution methods are developed and implemented. First, an integer linear programming formulation is derived for finding exact solutions. Second, a local-search heuristic for hypergraph partitioning is extended to cope with path-inequality constraints. Experimental results on a set of layer-assignment benchmarks demonstrated that the path-constrained local-search heuristic achieves optimum or near-optimum solutions with several orders of magnitude faster than the integer linear programming approach.     

The timetable constrained distance minimization problem

We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.