Christoph Buchheim

Title:
A slightly extended formulation for nonlinear 0/1 optimization problems

Abstract:
We present a new polyhedral approach to nonlinear 0/1 optimization problems. Compared to other methods, our approach yields much smaller models, making it more efficient from the practical point of view, especially on sparse instances. We obtain this improvement by two different ideas: first, we do not require the objective function to be in any normal form. The transformation into a normal form usually leads to the introduction of many additional variables or constraints. Second, we reduce the problem to the degree-two case in a compact way, using a slightly extended formulation. The resulting
model turns out to be closely related to the max-cut problem; we can show that the corresponding polytope is a face of a suitable cut polytope. In particular, our separation problem can be completely reduced to the separation problem for max-cut. Experimental results show that our branch-and-cut implementation of this approach is significantly faster than other methods.