Output details
11 - Computer Science and Informatics
University of St Andrews
Filtering Algorithms for the Multiset Ordering Constraint
<11>Constraint propagation algorithms capture frequently-occurring patterns of inference crucial to the efficiency of modern constraint solvers. The multiset ordering constraint is primarily applied to breaking symmetry in a constraint model, preventing the solver from exploring symmetric equivalents of dead ends encountered during search, which would vastly reduce performance. This paper builds on our highly influential body of work in symmetry breaking and propagator design. We pioneered development of symmetry-breaking constraints with lexicographic ordering. Multiset ordering is often more effective and the two can be combined into an efficient hybrid. This paper was published in the leading journal in Artificial Intelligence.