@inproceedings{7bd49497177148a98d05bb6312e70eb9,
title = "Global constraints for lexicographic orderings",
abstract = "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.",
author = "Alan Frisch and Brahim Hnich and Zeynep Kiziltan and Ian Miguel and Toby Walsh",
note = "Funding: This research was made possible by VR grant 221-99-369, EPSRC grant GR/N16129 and an EPSRC advanced research fellowship.; 8th International Conference on Principles and Practice of Constraint Programming, CP 2002 ; Conference date: 09-09-2002 Through 13-09-2002",
year = "2002",
month = jan,
day = "1",
doi = "10.1007/3-540-46135-3_7",
language = "English",
isbn = "9783540441205",
series = "Lecture notes in computer science",
publisher = "Springer-Verlag",
pages = "93--108",
editor = "Pascal Hentenryck",
booktitle = "Principles and practice of constraint programming",
address = "Germany",
}