DIMACS Workshop: Theory and Practice of Integer Programming in honor of Ralph E. Gomory on the Occasion of his 70th Birthday
August 2 - 4, 1999
IBM Watson Research Center, Yorktown Heights, NY
- William Cook, Rice University, firstname.lastname@example.org
- William Pulleyblank, IBM Watson Research Center, email@example.com
Integer Relaxations and Basis Reduction
For many integer and combinatorial optimization problems algorithms based on
linear relaxations, such as branch-and-cut, have been very successful.
In some cases though these methods fail. Here we present an approach
for solving integer programming problems based on integer relaxations.
To formulate the relaxations we use lattice basis reduction. We illustrate
the approach on a few problem types and attempt to give an idea why integer
relaxations may work better than linear relaxations for these problems. We
also report on some computational results.
This talk is based on joint work with Bob Bixby, Cor Hurkens, Arjen Lenstra,
and Job Smeltink.
Disjunctive Programming Revisited
Carnegie Mellon University
Mathematical drama in two acts.
Act I. Scene: the seventies.
Intersection cuts, outer polars, disjunctive cuts. The convex
hull of a union of polyhedra. Facial disjunctive sets, sequential
convexification. Monoidal cut strengthening. Poor computational
Act II. Scene: the nineties.
Disjunctive programming rediscovered. Reformulation-
linearization. Matrix cones. Lift-and-project. Cut lifting.
Implementation: branch-and-cut; restrict to subspace, lift
(reformulate), project back, lift and strengthen cuts. Major
computational success, at long last.
On the volume algorithm and some combinatorial linear programs
IBM T.J. Watson Research Center
We present an extension to the subgradient algorithm to produce primal as well
as dual solutions. It can be seen as a fast way to carry out an approximation
of Dantzig-Wolfe decomposition. This gives a fast method for producing
approximations for large scale linear programs. It is based on a new theorem
in linear programming duality. We present successful experience with large
linear programs coming from set partitioning, airline schedule planning,
facility location, Steiner tree problems, and max-cut.
Approximately Solving some Large-Scale Linear Programs
We present computational experience with an implementation of the
Grigoriadis-Khachiyan-Plotkin-Shmoys-Tardos exponential penalty method for
block-structured linear programs. Together with a procedure for strengthening
Lagrangian relaxations, this yields a fast approximation algorithm that
yields very promising results when applied to relaxations of large-scale
mixed-integer programs arising in network design.
Finiteness Proofs as of 1999
University of Illinois
Ralph Gomory's paper on cutting-plane methods for integer programs contains
the intriguing remark:
``...in all problems done so far, ANY method involving the
reduced inequalities has worked. It would be desirable to know
whether or not this is true in general.''
We investigate various aspects of this problem.
Gomory Cuts, Revisited
In this talk we discuss several computational experiments with Gomory cuts
on a wide range of general mixed-integer programs. We show that a
branch-and-cut system that incorporates these cuts can be used effectively
to solve problems that are not easily solvable without cutting planes. Our
results challenge the widely-held belief that Gomory cuts are numerically
unstable, and that they cannot be used effectively within commercial
software. This work was first presented in a meeting in Giens, France, in
Gomory Cuts and Combinatorial Reasoning
Department of Computer Science
Gomory's cutting-plane algorithms for integer linear programming
problems provide a framework for formalizing combinatorial proofs.
I will survey a few aspects of these cutting-plane proof systems.
Decomposition of Balanced Matrices
Carnegie Mellon University
A 0,1 matrix is balanced if it does not contain a square submatrix of odd order
with two ones per row and per column. In this talk, I will present a result
obtained in collaboration with M. Conforti and M. R. Rao. We show that a
balanced 0,1 matrix is totally unimodular or its bipartite representation has
a cutset consisting of two adjacent nodes and some of their neighbors. This
result yields a polytime recognition algorithm for balancedness.
Optimal 3-terminal Cuts and Linear Programming
William H. Cunningham
University of Waterloo
Given an undirected graph and three specified terminal nodes,
a 3-terminal cut is a subset of edges whose deletion leaves
the terminals in different components. The optimal 3-terminal
cut problem is the problem of finding such a set having minimum
weight. It is NP-hard, and in fact, is max-SNP-hard. Calinescu,
Karloff, and Rabani (1998) analyzed a certain integer linear
programming formulation, and showed that the ILP optimal value
is at most 6/5 times the LP optimal value. We improve this bound
to 12/11, and show that this is best possible. As a consequence,
we can find efficiently a feasible solution to the ILP of value
at most 12/11 times the optimal value.
This is joint work with Lawrence Tang, University of British Columbia.
Using a Parallel Branch Cut and Column Generation Framework to Solve Some
Difficult MIPLIB Problems.
IBM T.J. Watson Research Center
IBM Research has developed a Parallel Branch and Cut and/or Column generation
framework. In order to stress it, and test cut generators and column
generators, three of the miplib test set which have no published optimal
solutions were tackled. These were mkc, swath and seymour. In addition a
larger more realistic version of mkc (which comes from an IBM solution for Steel
Mills) was also attempted. The Parallel framework will be described and the
results achieved on the test set will be given.
Linear Programming Relaxations Arising from Cooperative Game Theory
Michel X. Goemans
We consider combinatorial optimization problems from a cooperative
game theory standpoint. The goal is to assign the total cost of a
project between the different participants, in such a way that no
group of participants, or coalition, is charged more than the cost of
the sub-project they induce on their own. We show that a canonical LP
relaxation plays a very special role. All the concepts are
illustrated on TSP games and facility location games.
Corner Polyhedra and their Connection with Cutting Planes.
Alfred P. Sloan Foundation
This talk will review the theory of Corner Polyhedra, point out some
of their properties and sructure, and show how knowledge of Corner
Polyhedra can be used to generate cutting planes for integer programming.
The connection iof Corner Polyhedra with cutting planes is through using
the fractional elements that appear in Gomory cuts not directly as
cutting planes but rather as group characters.
Peter L. Hammer
RUTCOR, Rutgers University
A Boolean Optimization problem is defined as the problem of
maximizing a real-valued linear function f(X), subject to g(X) = 0,
where X is a 0-1 vector, and g(X) is a Boolean function, assumed to
be given in disjunctive normal form. Typical problems of this type
include the weighted versions of the set covering, graph stability,
maximum satisfiability, and many other problems. Also, a wide class
of problems, including those of linear 0-1 programming, have readily
available relaxations in this class. The paper will present classes
of polynomially solvable problems, preprocessing methods, and
heuristic and exact algorithms for the solution of Boolean
optimization problems, along with some preliminary results obtained
in ongoing computational experiments, carried out jointly with Bela
Vizvari and Thomas Davoine.
Minimum Cuts in Networks
University of California at San Diego
We study the problem of getting minimum cuts without obtaining
maximum flows. We give various formulations for defining the
Gomory-Hu cut tree and random approximation algorithms.
Facets for Cycic Group Polyhedra and Knapsack Polytopes
Georgia Institute of Technology
Some theorems and examples from Gomory's group development and extensions
to knapsack problems will be presented. Connections between problems and
constructive ways to get facets will be emphasized.
ABACUS - A Branch-And-CUt System
In 1958, Ralph Gomory presented an elegant algorithmic solution to the
integer linear programming problem. He not only invented the cutting
plane method and proved its finiteness and correctness, but he also
implemented it on an E101 computer in order to see how it performs.
Today, branch-and-cut-and-price algorithms belong to the most
successful techniques for solving mixed integer linear programs and
combinatorial optimization problems to optimality (or, at least, with
certified quality). However, in the early eighties there were only
few computational studies due to the fact that implementing a
branch-and-cut-and-price algorithm from scratch requires a lot of
work, even with an LP-solver available. Since then, software systems
have been developed that facilitate the development of such software
by allowing the implementor to concentrate on the problem specific
parts only. The ever growing knowledge about algorithmic techniques
calls for much more convenient systems if we want to maintain the good
tradition in mathematical programming that new methods should be
demonstrated to actually solve the problems that led to their
development, in the spirit of George B. Dantzig, Ralph E. Gomory and
other pioneers in mathematical programming.
We observed that existing systems are strong for the solution of
general (mixed) integer optimization problems, but not as convenient
for the solution of hard combinatorial optimization problems as we
would like them to be. This was the ``algorithmic motivation'' for the
development of ABACUS, a software framework for the implementation of
branch-and-cut-and-price algorithms. We also recognized that the
realization of such a system in a non-object-oriented programming
language is difficult in its implementation, and---even
worse---inconvenient and unsafe in its application. The ``software
motivation'' for our work on ABACUS was that many of these problems
evaporate if object oriented design principles and programming
languages are used.
We briefly sketch the design criteria, the basic design ideas, and
the implementation of ABACUS in C++. Then we point out some
features of combinatorial optimization problems and show how they are
handled by ABACUS. Finally, we report on a variety of successful
applications of ABACUS.
Maximum Mean Weight Cycle and Cycle Optimization of Gigahertz Processors
University of Bonn
We consider the problem of finding an optimal clock schedule, i.e. optimal
arrival time for clock signal at latches of VLSI-chips. We show how to
optimize the cycle time and optimally balance slacks on datapaths and on
clock tree paths. We give a combinatorial algorithm, which solves this
problem optimally. This algorithm is an extension and modification of the
algorithm for the maximum mean weight cycle problem.
Designing Restorable Telecommunication Networks: A Variant of Gomory-Hu
Thomas L. Magnanti
In a classical 1961 paper, Gomory and Hu described a procedure for
designing a network with the least possible total capacity to meet
prescribed point-to-point demand between nodes of a potential network. We
consider a variant with an apparently modest twist: the demand between two
nodes cannot flow directly on an edge joining these nodes. This problem
arises in designing restorable telecommunication networks where the demand
corresponds to current flow and we wish to install spare capacity to
redirect flow, using alternative edges, when an edge fails. We examine the
polyhedral structure of an integer programming formulation of this problem
and report on computational experience in solving real world problems.
This talk is based on joint work with Yi Wang, I2 Technologies.
Large-scale Integer Programming in Airline Scheduling
George L. Nemhauser
Nearly 40 years ago, Paul Gilmore and Ralph Gomory did pioneering work
on delayed column generation techniques for solving the linear
programming relaxation of the cutting stock problem, which contains an
astronomical number of variables. Airline crew scheduling problems
also lead to models with an astronomical number (millions or billions)
of columns. Millions of dollars can be saved annually by obtaining
very high quality solutions to these models. We present recently
developed techniques for solving the linear programming relaxation and
0-1 integer programming model of these problems.
Small Polytopes and Branch & Cut
University of Heidelberg
Essential for the success of branch-and-cut algorithms for solving combinatorial
optimization problems are the availability of reasonable tight relaxations
and effective routines for solving the associated separation problems.
In this talk we discuss the concept of small instance relaxations
which can be particularly useful for problems with symmetric structure.
Small instance relaxations base on the facets of polytopes associated
with small instances of the combinatorial optimization problem to be solved
and can be generated automatically by facet enumeration.
For a certain class of symmetric problems, we
describe a general approach to the separation problem.
Algorithmic aspects of using small instance relaxations effectively
(parallel separation, facet selection, cutting plane selection)
are discussed in detail. Computational results are presented
for the linear ordering problem and a certain betweenness problem.
Gomory Cuts and Commercial Software
Martin W.P. Savelsbergh
Georgia Institute of Technology
For a long time, Gomory's seminal work on cutting planes has been considered
to be only of theoretical interest. However, this view has changed in the
last couple of years when implementations of branch-and-cut algorithms based
on Gomory cuts were shown to be able to successfully solve various difficult
integer programs. XPRESS-MP is among the few commercially available mixed
integer optimizers that has incorporated Gomory cuts in its default
branch-and-cut solver. In this talk, we present the results of a series of
computational experiments with XPRESS-MP's branch-and-cut solver and analyze
the value of Gomory cuts in the solution of difficult integer programs.
On Empty Lattice-Simplices
We study the complexity of deciding when given lattice-simplices are empty,
that is, do not contain lattice-points besides the vertices. We show how
some particular Gomory-Chv\'atal cuts provide good certificates
for this property in small dimensions.
The problem is embedded into a more general context of linear inequalities
satisfied by the so called `parallelepiped coefficients',
and the `Lonely Runner Problem' is formulated as a first application of these.
An improved lower bound for the maximum width of $n$-dimensional empty
simplices will also be shown.
Stable Set Polytopes and Rank One Constraints
We discuss two questions. How can one recognize if the stable set polytope of
a graph is not given by the rank-one constraints - starting from from the
clique inequalities? How can one recognize the infamous class of paritionable
graphs? Both questions appear to require a better understanding of the theory
of Gomory cuts.
Commutative Algebra and Integer Programming
University of California at Berkeley
During the past five years surprising interactions emerged
between integer programming theory and commutative algebra.
Grobner bases have been used to study and solve integer
programs, Gomory's group approach has been reexamined in terms
of localizations of toric ideals, and Scarf's work on test sets
has inspired significant developments on minimal free resolutions.
The purpose of this lecture is to present two specific new results,
which are important for the algebraic theory of integer programming:
(1) The six-dimensional counterexample found by Bruns and Gubeladze
for the Integer Caratheodory Property of Hilbert bases.
(2) The Chain Theorem proved by Hosten and Thomas for the
optimal points of a family of integer programs.
Adventures in Sports Scheduling
Carnegie Mellon University
The need to create quality sports schedules quickly in practice leads
to a number of interesting research directions. Work on schedules for
Major League Baseball and a number of college basketball leagues has
led to work in integer programming, including column generation
techniques based on the pioneering work of Gilmour and Gomory. Other
techniques used include network flows, matching, and constraint
New Separation Procedures for Vehicle Routing
We consider the capacitated vehicle routing problem (VRP): a fixed fleet of
delivery vehicles of uniform capacity must service at minimal transit cost
from a common depot known customer demand for a single commodity. This problem
is modeled as a side-constrained traveling salesman problem (TSP). Among the
additional constraints are the vehicle capacity restrictions, analogous to TSP
subtour elimination constraints. We present several variants of a
branch-and-cut algorithm for this VRP model, with separation methodology
for the capacity restrictions based on the TSP polyhedral relaxation.
Specifically, when standard procedures fail to separate a candidate point,
we attempt to separate it via decomposition into a convex combination of TSP
tours; if successful, the tours present in this decomposition are examined for
violated capacity restrictions, and if not, the Farkas Theorem provides a
hyperplane separating the point from the TSP polytope. Computational results
are given for an implementation the platform is the IBM SP2 of the Cornell
Theory Center. Our results include the first reported solution to optimality
of two large-scale VRP models taken from the standard literature for this
Hilbert bases in Integer Programming
Otto-von-Guericke Universit"at Magdeburg
It is known for many years that Hilbert bases play a central role
in Integer Programming.
Their applications range from totally dual integral systems
of inequalities over estimates of distances between
lattice points to simultaneous diophantine approximation
of rationals and the design of augmentation algorithms.
It is the latter application that will be central for the talk.
More precisely, we will analyze the geometry, complexity issues
and the combinatorics of augmentation algorithms.
Our analysis will show an analogy to cutting plane methods.
It will also provide a link to the fundamental work of Ralph Gomory.
Two-dimensional Gantt charts and a scheduling algorithm of Lawler
David P. Williamson
IBM T.J. Watson Research Center
In this talk I will give an alternate proof that a scheduling
algorithm of Lawler finds the optimal solution for scheduling a single
machine to minimize the weighted sum of completion time when the jobs
have precedence constraints that are series-parallel. To do this I
will use a linear programming formulation of this problem introduced
by Queyranne and Wang, and geometrical arguments based on what might
be called "two-dimensional Gantt charts". Queyranne and Wang proved
that their formulation completely describes the scheduling polyhedron
in the case of series-parallel constraints; a by-product of our proof
of correctness of Lawler's algorithm is an alternate proof of this
fact. It seems likely that these 2D Gantt charts may find independent
use, and to illustrate this I will show that some recent work in the
area becomes transparent using 2D Gantt charts.
Aggregation and Mixed Integer Rounding to solve MIPs
Laurence A. Wolsey
Mixed integer rounding (MIR) inequalities are essentially Gomory mixed
integer cuts. However it is important that MIR inequalities be generated
from constraints or aggregation of a small number of constraints of the
original problem in an attempt to use problem structure. This viewpoint
is strengthened by the observation that a variety of strong valid
inequalities derived earlier using structure are just such MIR
inequalities. Results are presented showing that a branch-and-cut
approach, based on a row aggregation heuristic to generate a knapsack
constraint with continuous variables, followed by generation of an MIR
inequality on the aggregate constraint, is effective in tacking a
variety of mixed integer
Many ``facets of complexity' of 0/1-polytopes and 0/1-programs
Gunter M. Ziegler
This will be a survey lecture about the geometry of 0/1-polytopes and
0/1-programs. These are complicated and complex in many different ways: for
example, the number of facets can be huge, the coefficients in their defining
inequalities may turn out to be huge, and the Chv\'atal-Gomory ranks may be
large. I also will try to explain why some of this complexity cannot be
detected in ``small examples.''
Contacting the Center
Document last modified on July 20, 1999.