| |
Various applications exist in which we need to optimize a non-linear
objective function over the vertices of a well-studied polytope as,
e.g., the matching polytope or the travelling salesman polytope (TSP).
Prominent examples are the quadratic assignment problem and the
quadratic knapsack problem; further applications occur in different
areas such as production planning or automatic graph drawing. In
order to apply branch-and-cut methods for the exact solution of such
problems, the objective function has to be linearized. However, the
standard linearization usually leads to very weak relaxations. On the
other hand, problem-specific polyhedral studies are often
time-consuming. Our goal is the design of general separation routines
that can replace detailed polyhedral studies of the resulting polytope
and that can be used as a black box.
In this talk, I will present three general separation methods. As
unconstrained binary quadratic optimization is equivalent to the
maximum cut problem, knowledge about cut polytopes can be used. Other
separation routines are inspired by the local cuts that have been
developed by Applegate, Bixby, Chvatal and Cook for faster solution of
large-scale traveling salesman instances. Finally, we apply quadratic
reformulations of the linear constraints as proposed by Helmberg,
Rendl and Weismantel for the quadratic knapsack problem.
I will show that a suitable combination of these methods leads to a
drastical speedup in the solution of constrained quadratic 0-1
problems.
This is joint work with C. Buchheim (TU Dortmund) and M. Oswald
(Heidelberg University)
|
