Browsing by Author "Miguel, Ian"

Now showing 1 - 2 of 2

Citation - WoS: 4
Citation - Scopus: 7
Filtering Algorithms for the Multiset Ordering Constraint
(Elsevier, 2009) Frisch, Alan M.; Hnich, Brahim; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby
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.
Citation - WoS: 25
Citation - Scopus: 34
Propagation Algorithms for Lexicographic Ordering Constraints
(Elsevier, 2006) Frisch, Alan M.; Hnich, Brahirn; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby
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.