Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2008/1095/

Berthold, Timo ; Heinz, Stefan ; Pfetsch, Marc E.

Solving Pseudo-Boolean Problems with SCIP

pdf-Format:
Dokument 1.pdf (437 KB) (Original Version MAR08) Dokument 2.pdf (438 KB) (Revised Version JUL09)
ps-Format:
Dokument 1.ps (773 KB) (Original Version MAR08) Dokument 2.ps (773 KB) (Revised Version JUL09)

Kurzfassung in Englisch

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.

Freie Schlagwörter (deutsch): Pseudo-Boolean , Constraint Programming , Ganzzahlige Programmierung , Branch-And-Cut , Optimierungssoftware
Freie Schlagwörter (englisch): Pseudo-Boolean , constraint integer programming , integer programming , branch-and-cut , optimization software
MSC - Klassifikation 90C11
MSC - Klassifikation 90C27
MSC - Klassifikation 65K05
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 08-12
ISBN: 1438-0064
Sprache: Englisch
Erstellungsjahr: 2008
Publikationsdatum: 03.03.2008
Bemerkung: printed version not available / keine gedruckte Version verfügbar

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: