Nonlinear Pseudo-Boolean Optimization: Relaxation or Propagation?

Abstract Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.

Authors

• Timo Berthold
• Stefan Heinz 0001
• Marc E. Pfetsch

Keywords

No keywords are indexed for this paper.