TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Nonlinear pseudo-Boolean optimization: relaxation or propagation? N2 - 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. T3 - ZIB-Report - 09-11 KW - Pseudo-Boolean KW - constraint integer programming KW - linear relaxation KW - separation algorithm KW - domain propagation Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11232 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Feydy, Thibaut A1 - Stuckey, Peter T1 - Rapid Learning for Binary Programs N2 - Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search. T3 - ZIB-Report - 10-04 KW - Ganzzahlige Programmierung KW - Constraintprogrammierung KW - Primalheuristik KW - Konfliktanalyse KW - constraint programming KW - integer programming KW - primal heuristic KW - conflict learning Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11663 SN - 1438-0064 ER -