Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 2
Zurück zur Trefferliste

Solving Pseudo-Boolean Problems with SCIP

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Timo BertholdORCiD, Stefan Heinz, Marc PfetschORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Branch-And-Cut; Constraint Programming; Ganzzahlige Programmierung; Optimierungssoftware; Pseudo-Boolean
Pseudo-Boolean; branch-and-cut; constraint integer programming; integer programming; optimization software
MSC-Klassifikation: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
Datum der Erstveröffentlichung:03.03.2008
Schriftenreihe (Bandnummer):ZIB-Report (08-12)
ISSN:1438-0064
ZIB-Reportnummer:08-12
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.