Explaining flow-based propagation.

Select |




Print


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)