8:45 AM /Salon A/B

Monday, May 20
## IP1

Continuous Techniques in Discrete Optimization

Branch-and-cut combined with problem-specific heuristics is, at present, the most successful solution technique for discrete optimization problems. This approach is based on investigations of the polyhedra associated with the discrete problems and utilizes the machinery of linear programming.
There are, however, cases where nonlinear models of the underlying integer program yield good exact or approximate solution techniques. Although methods such as Lagrangian relaxation and subgradient methods and eigenvalue techniques have been around for quite some while, the nonlinear approach is still a wide open field for research.

In this presentation, the speaker will describe the already mentioned "classical" techniques, but will particularly report about more recent advances where use is made of positive semidefinite forms and relaxations using polynomials of higher degrees.

**Martin Grotschel**

Konrad-Zuse-Zentrum and Technische Universitat

Berlin, Germany

*MEM, 3/11/96*