Nonlinear Methods for Combinatorial Optimization

linear programming. Good reasons for this choice are that the tightest convex
relaxation of the feasible points --- the convex hull --- can be described by
linear inequalities and that reliable and efficient software for solving
linear programs is readily available. The convex hull, however, is in general
difficult to obtain and for some problems, in particular with inherently
nonlinear constraints or cost functions, it is worth to consider nonlinear
relaxations.

Prominent examples are the semidefinite relaxations of quadratic 0-1
programming and graph partitioning problems. Their strong theoretical
properties aroused much interest, but, due to the lack of efficient software
for solving these relaxations, the approach is widely considered impractical.
The aim of much of my work is to advance computational methods for
semidefinite programming to the point, where solving semidefinite relaxations
is a matter of course, so that we can start with investigating the properties
and the quality of the relaxations in practice. In my talk I will give a short
introduction to semidefinite programming, sketch algorithmic approaches for
solving semidefinite programs, present first computational experiments on
semidefinite relaxations of graph partitioning problems enhanced by cutting
planes, and point out some directions for further research.

In industrial applications of combinatorial optimization the need for
considering nonlinear models arises from the fact that actual data is often
based on rough estimates or predictions. The fight for a provably optimal
solution for one instance is then purely academic, and I will briefly
illustrate this for a scheduling problem with setup times for printing
machines. The task of developing practically useful concepts for ``robust''
solutions, that work ``reliably well'', is at least as challenging and
important. In combinatorial optimization, the development of robust and
stochastic programming models is still in its beginnings and I plan to join
this effort in a new project on ``management of inter-warehouse-logistics for
stochastic demand''.