Affordable Access

Terse Integer Linear Programs for Boolean Optimization

Authors
Publication Date
Keywords
  • 03B70 Logic In Computer Science
  • 65K05 Mathematical Programming
  • 90C57 Polyhedral Combinatorics
  • Branch-And-Bound
  • Branch-And-Cut
Disciplines
  • Computer Science

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Dual formulations and subgradient optimization str...

on Discrete Applied Mathematics Jan 01, 1988

On the knapsack closure of 0-1 Integer Linear Prog...

on Electronic Notes in Discrete M... Jan 01, 2010
More articles like this..