PLENARY & KEYNOTE SPEAKERS

Egon Balas
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
Rice University

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 computational implications.

We will examine the above developments, with a particular emphasis on recent developments in computational research for MIP.

Brenda Dietrich
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.

Yurii Nesterov
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.