.png){kind=icon}
.png){kind=icon}
Return
Filtering algorithms for the multiset ordering constraint
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2008.11.001.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial. (C) 2008 Elsevier B.V. All rights reserved.
Keywords:
Constraint satisfaction
Constraint programming
Modelling
Global constraints
Constraint propagation
Propagation algorithms
Symmetry breaking
Multiset ordering
Leximin optimal solutions
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W
Organization
View more organizations