Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

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

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

Nonlinear pseudo-Boolean optimization: relaxation or propagation?

pdf-Format:
Dokument 1.pdf (412 KB)
ps-Format:
Dokument 1.ps (719 KB)

Kurzfassung in Englisch

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.

Freie Schlagwörter (englisch): Pseudo-Boolean, constraint integer programming, linear relaxation, separation algorithm, domain propagation
MSC - Klassifikation 90C10
MSC - Klassifikation 65K05
MSC - Klassifikation 90C09
MSC - Klassifikation 90C30
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 09-11
ISBN: 1438-0064
Quelle: Appeared in: O. Kullmann (Ed.), Theory and Applications of Satisfiability Testing -- SAT 2009; Lecture Notes in Computer Science 5584, pp. 441-446, 2009
Sprache: Englisch
Erstellungsjahr: 2009
Publikationsdatum: 29.03.2009
Bemerkung: printed version not available / keine gedruckte Version

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