Integer Programming Down Under: Theory, Algorithms and Applications

July 6—8, 2011

Newcastle NSW Australia

Sponsored by CARMA , AMSI, AustMS, and CMIS


The Gurobi Optimizer

Bob Bixby, Gurobi Optimization (slides)

Optimisation in a Coal Export Supply Chain

Natashia Boland, University of Newcastle. Joint work with Thomas Kalinowski, Hamish Waterer, and Lanbo Zheng (slides, video)

Newcastle is home to the world's largest coal export operation. Coal from around 40 mines is mined, transported, assembled and exported through 3 terminals at the port. This is a highly complex logistics operation, involving many companies, including producers (mining companies), rail track owners, above-rail (train) operators, terminal operators and the port corporation. In a landmark for collaborative logistics, a planning group, tasked with coordinated planning for the logistics operation, was established. Incorporated in 2010, this group became the Hunter Valley Coal Chain Coordinater P/L (HVCCC). In this talk, we give an overview of the research we have undertaken in collaboration with the HVCCC. In the case of long-term maintenance planning, elegant mathematical problems can arise. We discuss our progress on integer programming models and algorithms for maintenance scheduling.

Turbo-charging the Feasibility Pump

Faramroze G. Engineer, University of Newcastle. Joint work with Natashia L. Boland, Andrew C. Eberhard, Matteo Fischetti, and Martin W.P. Savelsbergh (slides)

The Feasibility Pump (FP) has proved to be an effective method for finding feasible solutions to Mixed-Integer Programming (MIP) problems. FP iterates between a rounding procedure and a projection procedure that together provide a sequence of points alternating between LP-relaxation feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimise the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them.

Recent advances using constraint propagation demonstrate that enhancements to the rounding procedure aimed at improving LP feasibility of the integer points can markedly improve the quality of feasible solutions found. Here we explore an alternative idea that generates many integer points at each FP iteration. We investigate the benefits of replacing the rounding procedure with a more sophisticated line search that efficiently explores a much larger neighbourhood of integer points close to an FP iterate. An extensive computational study on 1000+ benchmark instances demonstrates the effectiveness of the proposed approach.

Improved Integer Programming-Based Neighborhood Search for LTL Load Plan Design

Alan Erera, Georgia Tech (slides)

We present an improved very large-scale neighborhood search method for solving an extremely large integer programming (IP) model for service network design in the trucking industry, where neighborhoods are searched using time-limited integer programs. Less-than-truckload (LTL) carriers operate networks of consolidation terminals, and route each customer shipment through a sequence of terminal stops en route from origin to destination. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan for large LTL carriers determines the specific sequence of terminal stops to be used to transfer freight between each origin and destination. Service network design for LTL carriers requires building a load plan to minimize linehaul transportation and handling costs. In our solution method, we improve a given load plan sequentially via a neighborhood search in which potential load plan changes are identified by solving small integer programs to attract freight to or reduce freight from a specific terminal-to-terminal direct arc. Computational results using data from a large U.S. carrier show substantial cost improvements over the base load plans used in practice, as well as over our earlier approach that used neighborhoods that restricted changes to freight paths inbound to a single destination each iteration.

The Shift Minimisation Personnel Task Scheduling Problem

Andreas Ernst, CSIRO. Joint work with Mohan Krishnamoorthy and Davaatseren Baatar (slides)

We consider the problem of assigning tasks with fixed start and end times to workers. The set of workers that can perform a task is limited based on qualifications of the workers, shift times or other limitations. The aim is to create an assignment of all of the tasks which requires the least number of shifts. In this talk integer programming based algorithms are presented for obtaining both exact and heuristic solutions. The exact method relies on a novel branching method and column generation, while the heuristic algorithms are based on Lagrangian relaxation. Computational results demonstrate the effectiveness of these approaches.

Cuts from partial branch and bound trees

Daniel Espinoza, University of Chile (slides)

Branch and bound and cut is the most successful technique to tackle general mixed integer problems (MIP) since the breakthrough paper of Dantzig, Fulkerson and Johnson, where many of the nowadays standard techniques for MIP where introduced. However, the central part of the algorithm remains essentially an intelligent enumeration of the feasible space, and in general, once the branch and bound tree reaches a certain size, further improvement, either in upper or lower bound, disappear. This has prompted a series of papers on trying to avoid to create unnecessary branches, or to propagate infeasibility information from a particular branch to the rest of the tree. In this paper, we propose a different approach: namely, to summarize a given branch and bound tree as a set of cuts back at the root node problem. This is achieved algorithmically rather than algebraically, by using the ideas of Local Cuts as presented by Applegate et al.

Related questions, such as cut selection criteria, impact of using current technologies on top of our approach, are investigated. Finally, computational result are presented on a large set of instances coming from known publicly available test-sets.

Branch-and-Cut for Piecewise Linear Optimization and Extenisons

Ismael de Farias, Texas Tech University. Joint work with Ernee Kozyreff and Rajat Gupta (Texas Tech), and Ming Zhao (SAS) (slides, video)

Besides being important in its own right, piecewise linear optimization (PLO) can be used to approximate nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP). We give new inequalities valid for the PLO knapsack polytope and we present results of an extensive computational experimentation that establishes the importance of these cuts, and of PLO cuts (as opposed to general mixed-integer programming cuts) for solving PLO. In the process, we give new computational results that evaluate different formulations for PLO. Finally, we take our first step towards our goal of studying the approximation of NLP and MINLP through PLO. Specifically, we study the important case of PLO over sem-continuous variables. We show how to strenghten valid inequalities for PLO in this case, and we give computational results that demonstrate the usefulness of these (strengthened) cuts for PLO over semi-continuous variables.

1,2,3... QAP!

Matteo Fischetti, University of Padova. Joint work with Michele Monaci and Domenico Salvagnin (slides, video)

We address the exact solutions of the famous "esc" instances of the quadratic assignment problem. These are extremely hard instances that remained unsolved--even allowing for a tremendous computing power--by using all previous techniques from the literature. During this challenging task we found that three ideas were particularly useful and qualified as a breakthrough for our approach. The talk is about describing these ideas and their impact in solving esc instances.

Our method was able to solve, in a matter of seconds or minutes on a single PC, all easy cases (all esc16* plus esc32e and esc32g). The three previously-unsolved esc32c, esc32d and esc64a were solved in less than half an hour, in total, on a single PC. By using a facility-flow splitting procedure, we were also able to solve to proven optimality, again for the first time, esc32h (in about 2 hours) as well as "the big fish" esc128 (to our great surprise, the solution of the latter required just a few seconds on a single PC).

Algorithms for the Cross-dock Door Assignment Problem

Monique Guignard-Spielberg, University of Pennsylvania. Joint work with Peter Hahn, Yi-Rong Zhu, Ying Liu, Artur Alves Pessoa and Guilherme Henrique Ismael de Azevedo (slides)

In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to outgoing trucks, thus minimizing the distances that forklifts must travel. Optimizing strip and stack door assignments given the shape of the cross-dock and the origin-destination volumes of goods is known as the Cross-dock Door Assignment Problem (CDAP). We present a formulation of the CDAP as a Generalized Quadratic (3-dimensional) Assignment Problem. We then compare one approximate and two exact solution methods for optimizing door assignments at a small and a medium cross-dock, for artificially generated but realistic origin-destination volumes of trucked goods.

On a Fixed-Charge Grid Network Polyhedron

Simge Kucukyavuz, Ohio State University. Joint work with Minjiao Zhang and Hande Yaman (slides)

In this talk, we study an uncapacitated fixed-charge network problem on a grid, which arises in multi-echelon lot sizing in series with intermediate demands. We give a polynomial-time dynamic programming algorithm and a tight, compact extended formulation for 2-echelon ULS (2-ULS). Next, we present a family of valid inequalities for multi-echelon ULS, show its strength and give a polynomial-time separation algorithm. We establish a hierarchy between the alternative formulations for 2-ULS. In particular, we show that our valid inequalities can be obtained from the projection of the uncapacitated facility location formulation. Our computational results show that this extended formulation is very effective in solving our multi-item test problems.

Using Nested Column Generation and Generic Programming to solve Staff Scheduling Problems

Andrew Mason, The University of Auckland (slides)

We present a nested column generator and integer programming framework designed to solve a wide range of staff scheduling problems. We use generic programming principles to allow column-time customisation, giving significantly improved run times. Results are presented on a range of strategies designed to further reduce run times, including neighbourhood constrained column generation, as applied to instances from the 2010 International Nurse Rostering Competition.

Cutting Planes for Stochastic Integer Programs

George L. Nemhauser, School of Industrial and Systems Engineering, Georgia Institute of Technology (slides, video)

Two approaches for dealing with uncertain data in optimization are stochastic and chance-constrained programming. We first consider multi-stage stochastic integer programs and we give a general method for generating new cutting planes based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem and to stochastic lot sizing problems.

Linear programs with joint probabilistic constraints (PCLP) are known to be highly intractable due to the non-convexity of the feasible region. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We present a mixed integer programming formulation and study the relaxation corresponding to a single row of the probabilistic constraint, yielding two strengthened formulations.

We give computational results that show that these new inequalities are very effective in a branch-and-cut algorithm and large-scale instances can be solved to optimality.

Multi-objective integer programming: An improved recursive algorithm

Melih Ozlen, RMIT. Joint work with Benjamin A. Burton (slides)

This study introduces an improved recursive algorithm to generate the set of all nondominated objective vectors for the Multi-Objective Integer Programming problem. We significantly improve the earlier recursive algorithm of Özlen and Azizoglu by using the set of already solved subproblems and their solutions to avoid solving a large number of IPs. We conduct a series of randomised computational experiments to show the amount of savings that can be obtained by this improved algorithm.

Iron Ore Production and Logistics Planning via Integer Programming

Marcus Poggi, PUC-Rio. Joint work with Marcelo Reis, Cristiane Ferreira, Mario Lobato, André Lima (GAPSO Inc.) (slides1,slides2)

We address the problem of planning the operations of an iron mining company. This problem aims at delivering the clients demands for ore quantities with specific characteristics such as percentages of iron and of silica in the product. Demands are spread over time and their required product is obtained from a mix of ore extracted from different mines. The mines are spread over space and have very different lead time to the delivery port. This scenery leads to a planning problem where blending structure of a "diet problem" over a network flow meets the scheduling of lots of a fixed size. The capacity of handling and of straining machines as well as the capacities of the yards and the rates of unloading and loading along the network must be considered. The objective is to provide medium and short terms plans which consider unit periods of month and day, respectively. The medium term horizon is usually one year, although three year plans are analyzed from time to time. For the short term a plan with a horizon of one month is to be provided and adjusted weekly. Short term plans are sometimes demanded to look for a horizons of six months.

The resolution method that can be reduced to a MIP model for the medium term, requires breaking and decomposing the problem for the short term using a relax and fix method. The idea is to take a date as the end of the horizon and try to fulfill all the demands until that date. All the fulfilled demands are fixed and we go sliding that date until it reaches the original horizon. After this, we have an improvement step. This step consists of selecting and fixing a set of variables and solving the fixed problem, trying to improve the solution. We repeat this step until the time limit is reached.

Workforce management in periodic routing problems

Karen Smilowitz, Northwestern University. Joint work with Maciek Nowak (slides, video)

Periodic routing problems involve the routing of vehicles to serve customers over a given time horizon. The set of customers to be visited changes over the time horizon; therefore, the workload of each driver may change each day. At the same time, it is also desirable to maintain a certain level of consistency in each drivers workload, to improve both efficiency and customer service. In this talk, we present a range of models for periodic routing problems. The models are connected by the way in which travel cost is balanced with workforce metrics that capture the consistency of driver routes. We analyze solutions derived from the various models and explore how the relationships among models may be used to improve solution approaches.

Generalising Algorithm Performance in Instance Space

Kate Smith-Miles, Monash University. Joint work with Leo Lopes (slides)

It is standard practice to compare the performance of optimisation algorithms on a set of chosen instances (benchmark, real-world, randomly generated, etc.) and draw conclusions about the superiority of one algorithm over others. The conclusions are likely to vary depending on the chosen instances and their characteristics. We are interested in providing new tools to researchers to enable them to report the performance they can expect from an algorithm, generalised across a broader instance space with diverse characteristics. This will help to identify the true strengths and weaknesses of algorithms. We propose a methodology for defining a high-dimensional instance space defined by measurable characteristics of the instances, which can then be visualised by projecting instances onto a 2-dimensional plane. The performance of algorithms in this plane is then superimposed and algorithm "footprints" can be visualised, providing the boundary in instances space where an algorithm is expected to perform well. We illustrate the methodology with a case study based on university timetabling.

Heuristics and MILP models

M. Grazia Speranza, University of Brescia (slides)

The size of MILP models solvable to optimality has been constantly increasing over time, due to technological and algorithmic progress. However, for several MILP models, instances of realistic size remain unsolvable to optimality within an acceptable amount of time. In this talk, I will present and discuss a heuristic framework of wide applicability that is based upon the optimal solution of MILP sub-problems and more specific heuristics that use the optimal solution of MILP models to intensify the search on promising regions of the solution space.

Lagrangian Decomposition and MIQP Reformulations for Probabilistic Constrained Quadratic Programs

Xiaoling Sun, School of Management, Fudan University (slides)

Probabilistic constrained quadratic programming (PCQP) problems arise from many real-world applications and have posed a great challenge due to the nonconvex and discrete nature of the feasible sets. We investigate in this talk a special case of PCQP with a finite discrete distribution for the random vector. We first derive a second-order cone programming (SOCP) relaxation and a semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. Preliminary computational results are reported to demonstrate the tightness of the convex relaxations and the effectiveness of the MIQP reformulation.

A new class of extended formulations for the Survivable Network Design with Hop Constraints Problem

Eduardo Uchoa, Fluminense Federal University. Joint work with A. Ridha Mahjoub and L. Simonetti (slides)

Given an undirected graph G and a set of pairs of vertices D, the SNDH problem consists in finding a minimum cost subgraph of G containing K edge-disjoint paths with length at most H linking each pair of vertices in D. The parameter K controls the desired level of survivability, while H is related to Quality of Service requirements. The SNDH problem is notoriously hard, current network design techniques have trouble on instances with only 20 vertices. We present hop-level-MCF, a new class of extended formulations built upon the concept of solution levels. The linear relaxation of hop-level-MCF obtains lower bounds significantly better than those by previous formulations, allowing the solution of open instances from the literature.

Column Generation for Extended Formulations

Francois Vanderbeck, University of Bordeaux. Joint work with R. Sadykov (slides)

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools and derive valid inequalities for the original formulation, or consider an approximate extended formulation (f.i. by aggregating variables). Both approaches result in outer approximations of the intended extended formulation. An alternative is to work with inner approximations defined and improved by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which the original problem extended formulation is derived. Then, one can implement column generation for this extended formulation by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. Such "column-and-row generation" procedure is reviewed and analysed herein. We compare numerically a direct handling of the extended formulation, a standard column generation approach, and the "column-and-row generation" procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.

Keywords: Extended formulations for MIP, Column-and-Row Generation, Stabilization.