Solving Pseudo-Boolean Problems with SCIP
Please always quote using this URN: urn:nbn:de:0297-zib-10671
- Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.
Author: | Timo BertholdORCiD, Stefan Heinz, Marc PfetschORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | Branch-And-Cut; Constraint Programming; Ganzzahlige Programmierung; Optimierungssoftware; Pseudo-Boolean Pseudo-Boolean; branch-and-cut; constraint integer programming; integer programming; optimization software |
MSC-Classification: | 65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
Date of first Publication: | 2008/03/03 |
Series (Serial Number): | ZIB-Report (08-12) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 08-12 |