Global Constraints for Lexicographic Orderings

Alan M. Frisch; Brahim Hnich; Zeynep Kiziltan; Ian Miguel; Toby Walsh

doi:10.1007/3-540-46135-3_7

Global Constraints for Lexicographic Orderings

Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh

Computer Science

Research output: Contribution to conference › Paper › peer-review

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.

Original language	Undefined/Unknown
Pages	93-108
DOIs	https://doi.org/10.1007/3-540-46135-3_7
Publication status	Published - 2002

Access to Document

10.1007/3-540-46135-3_7

http://link.springer.de/link/service/series/0558/bibs/2470/24700093.htm

Cite this

@conference{55c2c1f4a1614b6995837f44a1659853,

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 = "Frisch, {Alan M.} and Brahim Hnich and Zeynep Kiziltan and Ian Miguel and Toby Walsh",

year = "2002",

doi = "10.1007/3-540-46135-3_7",

language = "Undefined/Unknown",

pages = "93--108",

}

TY - CONF

T1 - Global Constraints for Lexicographic Orderings

AU - Frisch, Alan M.

AU - Hnich, Brahim

AU - Kiziltan, Zeynep

AU - Miguel, Ian

AU - Walsh, Toby

PY - 2002

Y1 - 2002

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.

U2 - 10.1007/3-540-46135-3_7

DO - 10.1007/3-540-46135-3_7

M3 - Paper

SP - 93

EP - 108

ER -