×

zbMATH — the first resource for mathematics

Propagation algorithms for lexicographic ordering constraints. (English) Zbl 1131.68521
Summary: 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.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Carlsson, N. Beldiceanu, Arc-consistency for a chain of lexicographic ordering constraints, Technical Report T2002-18, Swedish Institute of Computer Science, 2002
[2] M. Carlsson, N. Beldiceanu, Revisiting the lexicographic ordering constraint, Technical Report T2002-17, Swedish Institute of Computer Science, 2002
[3] Cheng, B.M.W.; Choi, K.M.F.; Lee, J.H.M.; Wu, J.C.K., Increasing constraint propagation by redundant modeling: an experience report, Constraints, 4, 167-192, (1999) · Zbl 0949.68605
[4] Colbourn, C.H.; Dinitz, J.H., The CRC handbook of combinatorial designs, (1996), CRC Press · Zbl 0836.00010
[5] J. Crawford, G. Luks, M. Ginsberg, A. Roy, Symmetry breaking predicates for search problems, in: Proceedings of the 5th International Conference on Knowledge Representation and Reasoning (KR ’96), 1996, pp. 148-159
[6] P. Brisset, H. El Sakkout, T. Frühwirth, C. Gervet, W. Harvey, M. Meier, S. Novello, T. Le Provost, J. Schimpf, K. Shen, M.G. Wallace, ECLiPSe Constraint Library Manual Release 5.6, 2003
[7] Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR spektrum, 22, 425-460, (2000) · Zbl 1017.90096
[8] Flener, P.; Frisch, A.M.; Hnich, B.; Kiziltan, Z.; Miguel, I.; Pearson, J.; Walsh, T., Breaking row and column symmetry in matrix models, (), 462-476
[9] P. Flener, A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh, Matrix modelling: Exploiting common patterns in constraint programming, in: Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems, 2002, pp. 27-41
[10] Frisch, A.M.; Hnich, B.; Kiziltan, Z.; Miguel, I.; Walsh, T., Global constraints for lexicographic orderings, (), 93-108
[11] Gent, I.P.; Irving, R.W.; Manlove, D.; Prosser, P.; Smith, B.M., A constraint programming approach to the stable marriage problem, (), 462-476
[12] I.P. Gent, P. Prosser, B.M. Smith, A 0/1 encoding of the gaclex constraint for pairs of vectors, in: Notes of the ECAI-02 Workshop W9 Modelling and Solving Problems with Constraints, 2002
[13] I.P. Gent, T. Walsh, CSPLib: A benchmark library for constraints, Technical Report APES-09-1999, 1999
[14] W. Harvey, Personal e-mail communication, 2002
[15] B. Hnich, Function variables for constraint programming, PhD thesis, Department of Information Science, Uppsala University, 2003 · Zbl 1159.68390
[16] ILOG S.A., ILOG Solver 5.3 Reference and User Manual, 2002
[17] Z. Kiziltan, Symmetry breaking ordering constraints, PhD thesis, Uppsala University, 2004
[18] Mackworth, A.K., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[19] A.K. Mackworth. On reading sketch maps, in: Proceedings of the 5th International Joint Conference on Artificial Intelligence, 1977, pp. 598-606
[20] Meseguer, P.; Torras, C., Solving strategies for highly symmetric csps, (), 400-405
[21] Proll, L.; Smith, B.M., Integer linear programming and constraint programming approaches to a template design problem, INFORMS journal on computing, 10, 3, 265-275, (1998) · Zbl 1034.90518
[22] Puget, J.F., On the satisfiability of symmetrical constrained satisfaction problems, (), 350-361
[23] Schrijver, A., Theory of linear integer programming, (1986), John Wiley and Sons · Zbl 0665.90063
[24] Smith, B.M.; Brailsford, S.C.; Hubbard, P.M.; Williams, H.P., The progressive party problem: integer linear programming and constraint programming compared, Constraints, 1, 119-138, (1996)
[25] Shlyakhter, I., Generating effective symmetry-breaking predicates for search problems, Electronic notes in discrete mathematics, 9, (2001) · Zbl 1158.68497
[26] Swedish Institute of Computer Science, SICStus Prolog User’s Manual, Release 3.10.1, April 2003
[27] Wallace, M., Practical applications of constraint programming, Constraints, 1, 1/2, 139-168, (1996)
[28] Walser, J.P., Integer optimization by local search—A domain-independent approach, Lecture notes in artificial intelligence, vol. 1637, (1999), Springer · Zbl 0934.90053
[29] Wallace, M.G.; Novello, S.; Schimpf, J., Eclipse: A platform for constraint logic programming, ICL systems journal, 12, 1, 159-200, (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.