HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
October 14-19, 2002

2002-2003 Program: Optimization

Karen Aardal (School of Industrial and Systems Engineering, Georgia Institute of Technology)  aardal@math.uu.nl

Lattice Basis Reduction and Integer Programming    Papers:    journal.pdf    journal.ps    ut6n.pdf    ut6n.ps

We will review some of the main algorithmic ideas behind the use of lattice basis reduction to solve integer programming and related problems. We also discuss some computational issues related to the use of such methods. One issue is the amount of work spent in determining good branching directions. We present some computational results, useful computer packages available, and a number of open problems.


K. Aardal, R. Weismantel, and L.A. Wolsey. Non-standard approaches to integer programming. Discrete Applied Mathematics 123, 2002, 5-74.

K. Aardal and A.K. Lenstra. Hard equality constrained integer knapsacks Preprint 1256, Department of Mathematics, Utrecht University, 2002, (submitted). Preliminary version appeared in: W.J. Cook and A.S. Schulz (eds.), Integer Programming and Combinatorial Optimization: 9th International IPCO Conference, Lecture Notes in Computer Science vol. 2337, Springer-Verlag, 2002, pp 350-366.

David Applegate (AT&T Labs - Research)  david@research.att.com

Solving Random Euclidean TSPs

I will present computational results on solving random euclidean TSPs, with up to 2500 nodes, using the TSP solver Concorde. This is joint work with Bob Bixby, Vasek Chvátal, and Bill Cook.

Francisco Barahona (IBM T.J. Watson Research Center)  barahon@us.ibm.com

Network Reinforcement     Paper:    pdf

Given a weighted graph G=(V,E) , we study the question of finding a minimum cost subgraph that contains k disjoint spanning trees. We give an algorithm whose complexity is the same as solving |V| minimum cut problems. Previously known algorithms for this require solving |E| minimum cut problems.

Daniel Bienstock (Dept. of IEOR, Columbia University)  dano@ieor.columbia.edu  http://www.ieor.columbia.edu/~dano

Subset Algebra Lifting    Slides:    pdf

More than ten years ago, Lovasz and Schrijver proposed a formal framework for solving 0-1 integer programs that relies on the idea of "lifting" n-dimensional 0-1 vectors to 0-1 vectors in a space of much higher dimension. This process is advantageous in that the lifting reveals the structure of a 0-1 integer program in a more explicit way than the original formulation. The work of Lovasz and Schriver was itself motivated by earlier (special-case) work by Balas, Pulleyblank, Barahona and others. In the Lovasz-Schrijver approach, the target space of the lifting is the subset lattice of an n-element set. This method, and related work by Sherali and Adams (and later by Lasserre) have attracted attention in that the resulting relaxations provably satisfy nice properties.

In this talk we present a procedure that instead lifts to the subset-algebra of an n-element set. This method yields far stronger algorithms. For example, we obtain polynomial-time algorithms for solving the relaxation of a set-covering problem over the convex hull of all inequalities with small coefficients.

This is joint work with Mark Zuckerberg (Columbia).

Vasek Chvatal (Department of Computer Science, Rutgers University)  chvatal@cs.rutgers.edu

TSP Cuts that Do Not Follow the Template Paradigm

The first computer implementation of the Dantzig-Fulkerson-Johnson cutting-plane method for solving the traveling salesman problem, written by Martin, used subtour inequalities as well as cutting planes of Gomory's type. The practice of looking for and using cuts that match prescribed templates in conjunction with Gomory cuts was continued in computer codes of Miliotis, Land, and Fleischmann.

Groetschel, Padberg, and Hong advocated a different policy, where the template paradigm is the only source of cuts; furthermore, they argued for drawing the templates exclusively from the set of linear inequalities that induce facets of advocated a different policy, where the template paradigm is the only source of cuts; furthermore, they argued for drawing the templates exclusively from the set of linear inequalities that induce facets of the TSP polytope. These policies were adopted in the work of Crowder and Padberg, in the work of Groetschel and Holland, and in the work of Padberg and Rinaldi; their computer codes produced the most impressive computational TSP successes of the nineteen eighties. Eventually, the template paradigm became the standard frame of reference for cutting planes in the TSP.

I will outline a technique for finding cuts that disdains all understanding of the TSP polytope and bashes on regardless of all prescribed templates. Combining this technique with the traditional template approach in Concorde - a computer code written by David Applegate, Bob Bixby, Bill Cook, and myself -- was a crucial step in our solution of a 13,509-city TSP instance and a 15,112-city TSP instance.

Ismael Regis de Farias Jr. (Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213)  defarias@andrew.cmu.edu

Semi-Continuous Cuts for Mixed-Integer Programming

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming, problems with partial integer variables, and discrete optimization. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for mixed-integer programming, problems with partial integer variables, discrete optimization, and problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectivelly semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.

Jacques Desrosiers (HEC Montréal, GERAD et Méthodes quantitatives de gestion, 3000 Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7)  Jacques.Desrosiers@hec.ca

Stabilized Column Generation Based on Primal and Dual Strategies    Slides:    html    pdf    ppt

The perturbed version of a linear problem introduces bounded surplus and slack variables. To account for an available trust region on the dual space, these additional variables are penalized in the objective function of the primal formulation. This results in a stabilized version of the problem to solve. We present several theoretical aspects of a stabilized column generation approach and some recent computational results. The proposed procedure is also suitable for the so-called crossover from an optimal interior point solution to an optimal extreme point or basic solution.

Michel Gendreau (Centre for Research on Transportation and Département d'informatique et de recherche opérationnelle, Université de Montréal)  michelg@crt.umontreal.ca

A Column Generation Approach for Vehicle Routing with Time Windows and Split Deliveries?    Slides

In this talk, we will discuss the Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW), a variant of the well-known Vehicle Routing Problem with Time Windows in which a customer's demand can be split among several vehicles. We will first examine some properties of split delivery solutions and restate a direct mixed integer programming formulation for the problem. The main part of the presentation will be devoted to the description of a new column generation approach for solving the SDVRPTW without imposing any restrictions on the split delivery options. Computational results on problems with up to 50 customers will be reported and analyzed.

Jean-Louis Goffin (Faculty of Management, McGill University, 1001 Sherbrooke Street West, Montréal, Québec, H3A 1G5, Canada)  jean-louis.goffin@.mcgill.ca

Analytic Centers Cutting Plane Methods and Mixed Integer Programming, with Extensions to Semi-definite Cuts

The most effective way to solve realistic MIPs (mixed integer programs) is branch and price, which is based on Lagrangean relaxation. Lagrangean relaxation provides better bounds than the traditional branch and bound method, which relax the integer requirement.

At every node of the B&B tree, a nondifferentiable convex function (NDO) needs to be optimized. The classical NDO techniques, such as the Dantzig-Wolfe decomposition algorithm or subgradient optimization, have weaknesses, such as unreliable convergence or the lack of a rigorous termination criterion. The analytic center cutting plane method (ACCPM) attempts to improve over this.

We will sketch a full branch and price method that uses extensions of ACCPM, including Ryan and Foster branching and hot starts at the child nodes, using a dual Newton method.

Numerical results will be presented in problems arising in supply chain optimization.

Extensions of Dantzig-Wolfe column generation to semi-definite cuts will also be described, and numerical results in eigenvalue optimization will be reported. This could be used in a branch and sdp-cut framework.

Joint work with Samir Elhedhli, Assistant Professor, Dept. of Management Sciences, University of Waterloo, 200 University W., Waterloo, On. and Mohammad R. Oskoorouchi, College of Business Administration, California State University, San Marcos, 333 S. Twin Oaks Valley Rd., San Marcos, California 92096-0001 USA.

Ralph E. Gomory (President, Alfred P. Sloan Foundation)  gomory@sloan.org

T-Space and Cutting Planes

In this paper we show how knowledge about T-Space translates directly into cutting planes for general integer programming problems. After providing background on Corner Polyhedra and on T-Space, this paper examines T-Space in some detail. It gives a variety of constructions for T-Space facets, all of which translate into cutting planes, and introduces continuous families of facets. In view of the great variety of possible facets, no one of which can be dominated either by any other or by any combination of the others, a figure of merit is introduced to provide guidance on their usefulness. T-Spaces based on higher dimensional groups are discussed briefly as is the idea of going beyond cutting planes to iterated approximations of Corner Polyhedra.

Zonghao Gu (ILOG, Inc.)  gu@ilog.com

One Size Fits All? Computational Tradeoffs in a Commercial Mixed Integer Programming Solver    Slides:    html    pdf    ppt

Mathematical modelers approach MIP software from a variety of different angles. Models can be challenging for a variety of reasons, some due mainly to combinatorial issues and others due to the difficulty of the relaxations. Modelers also often have different goals, with some requiring proven optimal solutions, others requiring good feasible solutions, and still others simply wanting to know if feasible solutions exist. A variety of techniques and strategies are available for addressing these problems, each of which is appropriate for some but often entirely inappropriate for others. Modelers are generally not interested in understanding the internal workings of the MIP solver, so the task of choosing a reasonable set of techniques to apply to a particular model falls to the MIP solver itself. This talk will discuss some of the more important and interesting computational tradeoffs that result.

Ellis Johnson (Industrial and Systems Engineering, Georgia Tech)  ellis.johnson@isye.gatech.edu

Cyclic Group and Knapsack Facets    Slides:    html    pdf    ppt

Any pure integer program can be relaxed to a cyclic group problem. We consider the master cyclic group problem and three versions of master knapsack problems, show the relationship between these problems, and give several classes of facet-defining inequalities for each problem, as well as mappings that take facets from on type of master polyhedron to another.

Alexander Martin (TU Darmstadt, FB Mathematik)  martin@mathematik.tu-darmstadt.de

Mixed Integer Models for the Optimization of Gas Networks    Slides:    pdf

A gas network basically consists of a set of compressors and valves that are connected by pipes. The task of the transient technical optimization is to optimize the drives of the gas and to set in the compressors cost-efficiently such that the required demands are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We approach it by approximating the non-linearities by piece-wise linear functions leading to a huge mixed integer program. We study the polyhedral consequences of this model and present some new cutting planes. Our preliminary computational results show the benefits when incorporating these cuts into a general mixed integer programming solver.

Rekha R. Thomas (University of Washington, Seattle)  thomas@math.washington.edu

The Structure of Group Relaxations

This talk will survey the main results on the structure of group relaxations that come from commutative algebra and discrete geometry. In particular, I will explain some of the open questions in this subject area and more generally, in the algebraic approach to integer programming. No familiarity with any of the algebraic methods is needed.

François Vanderbeck (Laboratoire de Mathématique Appliquées de Bordeaux (MAB), Université Bordeaux 1)  Francois.Vanderbeck@math.u-bordeaux.fr  http://www.math.u-bordeaux.fr/~fv/

A Generic View at the Dantzig-Wolfe Decomposition Approach in Mixed Integer Programming: Paving the Way for a Generic Code     Slides:    pdf

Commercial MIP solvers are becoming more and more powerful. Researcher must consider how MIP solvers can help us going further rather than compete against them. Dantzig-Wolfe decomposition approach to mixed integer programming can be seen as a way to push-back the limitations of MIP solvers by deferring the inevitable combinatorial explosion. However, this technique may seem not trivial to implement. Hence, there is a need for generic tools for implementing it.

The paper summarizes our views on the important components required to implement a Dantzig-Wolfe decomposition approach. A generic presentation of the methods paves the way for the elaboration of a generic code. In the process, we highlight the scope of this approach in Mixed Integer Programming (MIP).

The content includes a brief review the decomposition principle and the column generation reformulation it leads to. We see how to handle MIP as opposed to pure IPs. We present alternatives generating sets and the associated ways to enforce integrality. We introduce the concepts of proper columns and base patterns. We discuss state space relaxation. We consider multiple and nested decomposition and ways in which column generation can be combined with other efficient approaches to MIP. We conclude with a brief presentation of the prototype of our generic branch-and-price code, BaPCod.

Pascal Van Hentenryck (Department of Computer Science, Brown University)  pvh@cs.brown.edu

Local Search Programming

We present a three-level architecture for local search and its applications to large-scale optimization. The architecture is compositional and automates many of the tedious aspects of local search algorithms. In particular, it enables declarative specifications of the neighborhood which are compiled into efficient incremental algorithms. It also supports very high-level constructs for implementing heuristics and metaheuristics. The architecture is illustrated on several large-scale optimization problems in facility location and routing.

(Joint work with L. Michel).

Jean-Philippe Vial (Department of Management Studies, University of Geneva)  jean-philippe.vial@hec.unige.ch  http://ecolu-info.unige.ch/~logilab/vial/oldies/

Solving Lagrangian Relaxations with a Proximal Analytic Center Cutting Plane Method    Slides:    pdf

Joint work with O. du Merle, Air France.

Lagrangian relaxation, or its dual equivalent "column generation," is often used to generate lower bounds for integer programming problems, but solving the Lagrangian dual efficiently is sometimes an issue in itself. We propose a new cutting plane method, that can be interpreted as a compromise between the Analytic Center Cutting Plane Method (ACCPM, in short) and the Bundle method. We analyze the performance of the new method on the p-median problem, a special instance of partitioning problems.

Robert Weismantel (Department of Mathematics/IMO, Otto-von-Guericke-University of Magdeburg)  weismant@mail.Math.Uni-Magdeburg.De

Column Operations for Mixed Integer Programs

This talk deals with algorithmic approach for linear mixed integer programs. The essence of the algorithms to be discussed is a procedure that erases columns of the given program at the expense of introducing new columns corresponding to non-decomposable partial solutions. We discuss the general setting as well as a number of special cases such as the stable set problem. Computational results demonstrate the power and the generality of the approach.

2002-2003 Program: Optimization