Explaining flow-based propagation.
Downing, Nick; Feydy, Thibaut; Stuckey, Peter
2012-05-28
Conference Material
International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR)
Nantes, France
146-162
Lazy clause generation is a powerful approach to reducing search in constraint programming. For use in a lazy clause generation solver, global constraints must be extended to explain themselves. In this paper we present two new generic flow-based propagators (for hard and soft flow-based constraints) with several novel features, and most importantly, the addition of explanation capability. We discuss how explanations change the tradeoffs for propagation compared with the previous generic flow-based propagator, and show that the generic propagators can efficiently replace specialized versions, in particular for gcc and sequence constraints. Using real-world scheduling and rostering problems as examples, we compare against a number of standard Constraint Programming implementations of these contraints (and in the case of soft constraints, Mixed-Integer Programming models) to show that the new global propagators are extremely beneficial on these benchmarks.
network flow, constraint propagation, nurse rostering, car scheduling
http://www.emn.fr/z-info/cpaior-2012/
nicta:5486
Downing, Nick; Feydy, Thibaut; Stuckey, Peter. Explaining flow-based propagation.. In: International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR); Nantes, France. 2012-05-28. 146-162. http://hdl.handle.net/102.100.100/100694?index=1
Loading citation data...
Citation counts
(Requires subscription to view)