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

Organizers:

Organizers:

William Cook, Rice University, bico@caam.rice.edu

William Pulleyblank, IBM Watson Research Center, pblk@us.ibm.com

1.

Integer Relaxations and Basis Reduction

Karen Aardal
Utrecht University

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.


2.

Disjunctive Programming Revisited

Egon Balas
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
results.
     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.


3.

On the volume algorithm and some combinatorial linear programs

Francisco Barahona
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.


4.

Approximately Solving some Large-Scale Linear Programs

Dan Bienstock
Columbia University

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.


5.

Finiteness Proofs as of 1999

Charles Blair
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.


6.

Gomory Cuts, Revisited

Sebastian Ceria
Columbia University

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
1993.


7.

Gomory Cuts and Combinatorial Reasoning

Vasek Chvatal
Department of Computer Science
Rutgers University

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.


8.

Decomposition of Balanced Matrices

Gerard Cornuejols
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.


9.

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.


10.

Using a Parallel Branch Cut and Column Generation Framework to Solve Some
Difficult MIPLIB Problems.

John Forrest
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.


11.

Linear Programming Relaxations Arising from Cooperative Game Theory

Michel X. Goemans
MIT

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.


12.

Corner Polyhedra and their Connection with Cutting Planes.

Ralph Gomory
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.


13.

Boolean Optimization

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.


14.

Minimum Cuts in Networks

T.C. Hu
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.  


15.

Facets for Cycic Group Polyhedra and Knapsack Polytopes

Ellis Johnson
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.


16.

ABACUS - A Branch-And-CUt System

Michael Junger
Universitat Koln


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.


17.

Maximum Mean Weight Cycle and Cycle Optimization of Gigahertz Processors

Bernhard Korte
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.


18.

Designing Restorable Telecommunication Networks: A Variant of Gomory-Hu
Network Synthesis

Thomas L. Magnanti
MIT

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.


19.

Large-scale Integer Programming in Airline Scheduling

George L. Nemhauser
Georgia Tech

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.


20.

Small Polytopes and Branch & Cut

Gerhard Reinelt
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.


21.

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.


22.

On Empty Lattice-Simplices

Andras Sebo
IMAG, Grenoble

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.


23.

Stable Set Polytopes and Rank One Constraints

Bruce Shepherd
Lucent Technologies

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.


24.

Commutative Algebra and Integer Programming

Bernd Sturmfels
University of California at Berkeley


Abstract:

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.


25.

Adventures in Sports Scheduling

Michael Trick
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
programming.


26.

New Separation Procedures for Vehicle Routing

Les Trotter
Cornell University

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
problem.


27.

Hilbert bases in Integer Programming

Robert Weismantel
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.


28.

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.


29.

Aggregation and Mixed Integer Rounding to solve MIPs

Laurence A. Wolsey
CORE

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
programming problems.


30.

Many ``facets of complexity' of  0/1-polytopes and 0/1-programs

Gunter M. Ziegler
TU Berlin


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.''

Other Workshops

DIMACS Homepage