TY - GEN
T1 - Global constraints for lexicographic orderings
AU - Frisch, Alan
AU - Hnich, Brahim
AU - Kiziltan, Zeynep
AU - Miguel, Ian
AU - Walsh, Toby
N1 - Funding: This research was made possible by VR grant 221-99-369, EPSRC grant GR/N16129 and an EPSRC advanced research fellowship.
PY - 2002/1/1
Y1 - 2002/1/1
N2 - We propose some global constraints for lexicographic orderings on vectors of variables. These constraints are very useful for breaking a certain kind of symmetry arising in matrices of decision variables.We show that decomposing such constraints carries a penalty either in the amount or the cost of constraint propagation. We therefore present a global consistency algorithm which enforces a lexicographic ordering between two vectors of n variables in O(nb) time, where b is the cost of adjusting the bounds of a variable. The algorithm can be modified very slightly to enforce a strict lexicographic ordering. Our experimental results on a number of domains (balanced incomplete block design, social golfer, and sports tournament scheduling) confirm the efficiency and value of these new global constraints.
AB - We propose some global constraints for lexicographic orderings on vectors of variables. These constraints are very useful for breaking a certain kind of symmetry arising in matrices of decision variables.We show that decomposing such constraints carries a penalty either in the amount or the cost of constraint propagation. We therefore present a global consistency algorithm which enforces a lexicographic ordering between two vectors of n variables in O(nb) time, where b is the cost of adjusting the bounds of a variable. The algorithm can be modified very slightly to enforce a strict lexicographic ordering. Our experimental results on a number of domains (balanced incomplete block design, social golfer, and sports tournament scheduling) confirm the efficiency and value of these new global constraints.
UR - https://doi.org/10.1007/3-540-46135-3
UR - https://www.scopus.com/pages/publications/84957030779
U2 - 10.1007/3-540-46135-3_7
DO - 10.1007/3-540-46135-3_7
M3 - Conference contribution
AN - SCOPUS:84957030779
SN - 9783540441205
T3 - Lecture notes in computer science
SP - 93
EP - 108
BT - Principles and practice of constraint programming
A2 - Hentenryck, Pascal
PB - Springer-Verlag
CY - Heidelberg
T2 - 8th International Conference on Principles and Practice of Constraint Programming, CP 2002
Y2 - 9 September 2002 through 13 September 2002
ER -