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.     

Lower bounds for the ITC-2007 curriculum-based course timetabling problem

This paper describes an approach for generating lower bounds for the curriculum-based course timetabling problem, which was presented at the International Timetabling Competition (ITC-2007, Track 3). So far, several methods based on integer linear programming have been proposed for computing lower bounds of this minimization problem. We present a new partition-based approach that is based on the “divide and conquer” principle. The proposed approach uses iterative tabu search to partition the initial problem into sub-problems which are solved with an ILP solver. Computational outcomes show that this approach is able to improve on the current best lower bounds for 12 out of the 21 benchmark instances, and to prove optimality for 6 of them. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches.     

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.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

Orbital branching

We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.     

The minimum distance superset problem: formulations and algorithms

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.     

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.     

A genetic algorithm solution for one-dimensional bundled stock cutting

This paper discusses a one-dimensional cutting stock problem in which lumber is cut in bundles. The nature of this problem is such that the traditional approaches of linear programming with an integer round-up procedure or sequential heuristics are not effective. A good solution to this problem must consider trim loss, stock usage and ending inventory levels. A genetic search algorithm is proposed and results compared to optimal solutions for an integer programming formulation of the problem.     

Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method

In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.     

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.     

Examining Optimal Criterion Weights in Mixed Integer Programming Approaches to the Multiple-group Classification Problem

Several mixed integer programming approaches to the multiple-group statistical classification problem are examined. Many papers have investigated conditions under which a degenerate solution occurs in linear programming approaches to the two-group discriminant problem. Very little research has been conducted in the multiple-group case. We investigate conditions under which a degenerate solution can occur in mixed integer programming approaches to the multiple-group classification problem. A multiple-group ‘minimize the sum of deviations’ model is presented. This model is similar in structure to the general single function classification model. Also, a two-goal approach to the multiple-group classification problem is discussed.     

A MIP-based framework and its application on a lot sizing problem with setup carryover

In this paper we present a framework to tackle mixed integer programming problems based upon a “constrained” black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to the original MIP formulation. Such corridors, or neighborhoods, are then explored, possibly to optimality, with a standard MIP solver. An iterative approach in the spirit of a hill climbing scheme is thus used to explore subportions of the solution space. While the exploration of the corridor relies on a standard MIP solver, the way in which such corridors are built around the incumbent solutions is influenced by a set of factors, such as the distance metric adopted, or the type of method used to explore the neighborhood. The proposed framework has been tested on a challenging variation of the lot sizing problem, the multi-level lot sizing problem with setups and carryovers. When tested on 1920 benchmark instances of such problem, the algorithm was able to solve to near optimality every instance of the benchmark library and, on the most challenging instances, was able to find high quality solutions very early in the search process. The algorithm was effective, in terms of solution quality as well as computational time, when compared with a commercial MIP solver and the best algorithm from the literature.     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous computers in an office environment, thus, drastically reducing the time required to find the solution.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

Integer programming to schedule a hierarchical workforce with variable demands

We consider a hierarchical workforce in which a higher qualified worker can substitute for a lower qualified one, but not vice versa. Daily labor requirements within a week may vary, but each worker must receive n off-days in the week. This problem has been considered by Hung (R. Hung, Eur. J. Oper. Res. 78(1) (1994) 49–57), who discusses a necessary and sufficient condition for a labor mix to be feasible and presents a simple one-pass method that frequently gives the least cost labor mix. We show in this paper that the integer programming approach is well suited for solving this problem: the definition of the integer programming model is simple, its implementation is immediate by using, for example, the Mathematical programming language (MPL) and the integer programming solver XA, the computation times are low (generally a few seconds on a small microcomputer) and finally the powerful of the integer programming approach allows us to extend the model in two interesting directions.     

整数规划的一类填充函数算法

填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。     

A mixed integer linear programming model for reliability optimisation in the component deployment problem

Component deployment is a combinatorial optimisation problem in software engineering that aims at finding the best allocation of software components to hardware resources in order to optimise quality attributes, such as reliability. The problem is often constrained because of the limited hardware resources, and the communication network, which may connect only certain resources. Owing to the non-linear nature of the reliability function, current optimisation methods have focused mainly on heuristic or metaheuristic algorithms. These are approximate methods, which find near-optimal solutions in a reasonable amount of time. In this paper, we present a mixed integer linear programming (MILP) formulation of the component deployment problem. We design a set of experiments where we compare the MILP solver to methods previously used to solve this problem. Results show that the MILP solver is efficient in finding feasible solutions even where other methods fail, or prove infeasibility where feasible solutions do not exist.     

Stochastic optimization for power system configuration with renewable energy in remote areas

This paper presents a stochastic mixed integer programming model for a comprehensive hybrid power system design problem, including renewable energy generation, storage device, transmission network, and thermal generators, for remote areas. Given the complexity of the model, we developed a Benders’ decomposition algorithm with two additional types of cutting planes: Pareto-optimal cuts generated using a modified Magnanti-Wong method and cuts generated from a maximum feasible subsystem. Computational results show significant improvement in our ability to solve this type of problem in comparison to a state-of-the-art professional solver. This model and the solution algorithm provide an analytical decision support tool for the hybrid power system design problem.     

Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables

This paper proposes an accelerated solution method to solve two-stage stochastic programming problems with binary variables in the first stage and continuous variables in the second stage. To develop the solution method, an accelerated sample average approximation approach is combined with an accelerated Benders’ decomposition algorithm. The accelerated sample average approximation approach improves the main structure of the original technique through the reduction in the number of mixed integer programming problems that need to be solved. Furthermore, the recently accelerated Benders’ decomposition approach is utilized to expedite the solution time of the mixed integer programming problems. In order to examine the performance of the proposed solution method, the computational experiments are performed on developed stochastic supply chain network design problems. The computational results show that the accelerated solution method solves these problems efficiently. The synergy of the two accelerated approaches improves the computational procedure by an average factor of over 42%, and over 12% in comparison with the original and the recently modified methods, respectively. Moreover, the betterment of the computational process increases substantially with the size of the problem.