Nonlinear methods in combinatorial optimization
by
Franz Rendl
University of Klagenfurt, Institute of Mathematics, A 9020 Klagenfurt, Austria

Linear relaxations of combinatorial optimization problems are by now a standard tool, and have reached the level of commercial software. Some NP-hard problems, like Max-Cut, Max-Clique or Quadratic Assignment have quite natural formulations as quadratic problems in binary variables. Rather than linearizing these formulations, it turns out to be of interest to work directly with the quadratic formulation.

We will review some of the most interesting ways to get nonlinear relaxations, leading to semidefinite programs. A key feature of all these relaxations lies in the fact that they allow strenghtening by including additional cutting planes. While the Linear-Programming based approach can handle huge numbers of constraints without serious complications, the situation is different for semidefinite models, where the number of constraints is a severe limit in practical computations. We will conclude with some computational experience, where Lagrangian relaxation, bundle methods, and semidefinite programming are combined to arrive at tight relaxations at low computational cost. Practical experience for Max-cut, graph-partition and the quadratic assignment problem will be provided, indicating the strong potential of this approach.

Date received: April 19, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cahh-09.