Universität zu Köln

Buchheim, Christoph ORCID: 0000-0001-9974-404X and Rinaldi, Giovanni ORCID: 0000-0003-0148-2470 (2009). Terse Integer Linear Programs for Boolean Optimization. Journal on Satisfiability, Boolean Modeling and Computation, 6. pp. 121-139.

Preview

PDF zaik2007-558.pdf - Draft Version Download (144kB) | Preview

Abstract

We present a new polyhedral approach to nonlinear boolean optimization problems. Compared to other methods, our approach produces much smaller integer programming models, making it more efficient from a practical point of view. We mainly obtain this 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 very efficient way, using a slightly extended formulation. The resulting model turns out to be closely related to the maximum cut problem; we show that the corresponding polytope is a face of a suitable cut polytope in most cases. In particular, our separation problem reduces to the one for the maximum cut problem. In practice, our approach turns out to be very competitive. First experimental results, which have been obtained for some particularly hard instances of the Max-SAT Evaluation 2007, show that our very general implementation can outperform even special-purpose SAT solvers.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED Rinaldi, Giovanni UNSPECIFIED orcid.org/0000-0003-0148-2470 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549211
Journal or Publication Title:	Journal on Satisfiability, Boolean Modeling and Computation
Volume:	6
Page Range:	pp. 121-139
Date:	2009
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54921