Dr. Christoph Buchheim
Institut für Informatik
Universität zu Köln

Stronger Relaxations for Nonlinear 0-1 Programming

We present a general approach for reducing nonlinear 0-1 optimization problems to quadratic 0-1 problems, based on integer programming techniques. The reduction can be applied after a slight extension of the variable space; the resulting polytope then turns out to be a face of a polytope corresponding to a quadratic instance of basically the same type. This allows to derive a polyhedral description for a general instance from the polyhedral description of an appropriate
uadratic problem.

In contrast to well-studied lift-and-project approaches, we aim at keeping the extended model as small as possible; our approach is particularly efficient for sparse problem instances. On the other hand, its implementation depends on a good separation algorithm for the resulting quadratic problem.

Besides explaining the general idea of the reduction, we will point out some connections to SDP approaches based on moment matrices. Moreover, we will give experimental results for unconstrained polynomial zero-one optimization problems and discuss further applications.