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
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.