2002-2003 Program: Optimization
Talk
Abstracts:
October
14-19, 2002
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.
References:
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
