On Using Cutting Planes in Pseudo-Boolean Optimization

Abstract

Cutting planes are a well-known, widely used, and very effective technique for Integer Linear Programming (ILP). However, cutting plane techniques are seldom used in Pseudo-Boolean Optimization (PBO) algorithms. This paper addresses the utilization of Gomory mixed-integer and clique cuts, in Satisfiability-based algorithms for PBO, and shows how these cuts can be used for computing lower bounds and for learning new constraints. A side result of learning new constraints is that the utilization of cutting planes enables non-chronological backtracking. Besides cutting planes, the paper also shows that the utilization of search restarts in PBO can be effective in practice, allowing the computation of tighter lower bounds each time the search restarts. The more aggressive lower bounds result from the constraints learned due to the utilization of cutting planes. Experimental results show that the integration of cutting planes and search restarts in a SAT-based algorithm for PBO yields a competitive new solution for PBO.