Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case

Buchheim, Christoph and Rinaldi, Giovanni (2007) Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case.
Published in: SIAM Journal on Optimization Vol. 18 (4). pp. 1398-1413.


We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation doesn't contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-503
Depositing User: Christoph Buchheim
Date Deposited: 12 Jun 2008 00:00
Last Modified: 17 Aug 2011 09:21
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/503