PLENARY & KEYNOTE SPEAKERS
Carnegie Mellon University
Computational Advances in Cutting Plane Theory
Recent advances in mixed integer programming (MIP) technology have produced a revolution in the state of the art: unlike in the past, most MIPs encountered in practice can now-a-days be solved. Cutting planes have played a central role in this revolution. Yet, useful as they are when embedded into a branch-and-bound framework, cutting planes by themselves are typically unable to solve instances of significant size. We examine the reasons for this, and discuss some lessons learned from studying rank 1 closures, from generating lift and project cuts from the LP simplex tableau, and from experimenting with a lexicographic cut generation procedure.
Robert E. Bixby
Recent Advances in Computational Linear and Mixed-Integer Programming
Computational methods for linear programming experienced
remarkable progress in the period from the late 1980s into the early
part of the current decade. These developments have led to the view
that, in practice, LP is largely a solved problem. However, progress
has slowed considerably in the last several years, and the effects are
beginning to show.
Developments in Mixed Integer Programming (MIP) have followed a
different path. Beginning with the introduction of the first
successful commercial codes for MIP in the early 1970s, through the late
1990s, commercial codes largely ignored the results of what was a truly
remarkable period of research in combinatorial optimization and integer
programming. That situation suddenly changed at the end of the 1990s,
with the result that MIP computation made a huge leap forward. This
trend has continued, and it has been accompanied by what appears to this
author to be a steadily increasing flow of research with important
We will examine the above developments, with a particular emphasis on
recent developments in computational research for MIP.
INFORMS President and IBM Research
Optimization Applications: New Opportunities and Challenges
In this talk I will address some emerging opportunities for the application
of optimization. These opportunities are enabled by years of advancement in
computing performance, by automation of business processes, by the
establishment of robust software libraries, and by the compilation of
vast data sets, There are also emerging challenges presented by new hardware
architectures and the need for near real time decision making. Examples
will be drawn from IBM projects.
CORE and Catholic University of Louvain (UCL), Belgium
Gradient methods for minimizing composite objective function
In this talk we present several methods for solving optimization problems
with the objective function formed as a sum of two convex terms: one is
smooth and given by a black-box oracle, and another is general but simple
and its structure is known. It appears that, despite to the bad properties
of the sum, such problems can be solved with efficiency typical for the good
part of the objective. For these problems, we consider primal and dual
variants of the gradient method (converges as O(1/k)),
and an accelerated multistep version, which
converges as O(1/k^2), where k is the iteration
counter. For all methods, we present very efficient "line search"
procedures and show that the additional computational work necessary for
estimating the unknown problem class parameters can only double the
complexity of each iteration.