Propagation Algorithms for Lexicographic Ordering Constraints

A.M. Frisch, B. Hnich, Z. Kiziltan, Ian James Miguel, T. Walsh

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

Abstract

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq. (c) 2006 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)803-834
Number of pages32
JournalArtificial Intelligence
Volume170
Issue number10
DOIs
Publication statusPublished - Jul 2006

Keywords

  • artificial intelligence
  • constraints
  • constraint programming
  • constraint propagation
  • lexicographic ordering
  • symmetry
  • symmetry breaking
  • generalized are consistency
  • matrix models

Fingerprint

Dive into the research topics of 'Propagation Algorithms for Lexicographic Ordering Constraints'. Together they form a unique fingerprint.

Cite this