1123
eng
reportzib
0
2009-03-29
2009-03-29
--
Nonlinear pseudo-Boolean optimization: relaxation or propagation?
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.
09-11
1438-0064
1172
urn:nbn:de:0297-zib-11232
Appeared in: O. Kullmann (Ed.), Theory and Applications of Satisfiability Testing -- SAT 2009; Lecture Notes in Computer Science 5584, pp. 441-446, 2009
Timo Berthold
unknown unknown
Stefan Heinz
Marc Pfetsch
ZIB-Report
09-11
eng
uncontrolled
Pseudo-Boolean
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear relaxation
eng
uncontrolled
separation algorithm
eng
uncontrolled
domain propagation
Mathematik
Mathematical programming methods [See also 90Cxx]
Boolean programming
Integer programming
Nonlinear programming
Mathematical Optimization
Berthold, Timo
Heinz, Stefan
https://opus4.kobv.de/opus4-zib/files/1123/ZR_09_11.pdf
https://opus4.kobv.de/opus4-zib/files/1123/ZR_09_11.ps