Skip to content

Research at St Andrews

Constraints for breaking more row and column symmetries

Research output: Contribution to journalArticle

Abstract

Constraint programs containing a matrix of two (or more) dimensions of decision variables often have row and column symmetries: in any assignment to the variables the rows can be swapped and the columns can be swapped without affecting whether or not the assignment is a solution. This introduces an enormous amount of redundancy when searching a space of partial assignments. It has been shown previously that one can remove consistently some of these symmetries by extending such a program with constraints that require the rows and columns to be lexicographically ordered. This paper identifies and studies the properties of a new additional constraint - the first row is less than or equal to all permutations of all other rows - that can be added consistently to break even more symmetries. Two alternative implementations of this stronger symmetry-breaking method are investigated, one of which employs a new algorithm that in time linear in the size of the matrix enforces the constraint that the first row is less than or equal to all permutations of all other rows. It is demonstrated experimentally that our method for breaking more symmetries substantially reduces search effort.

Close

Details

Original languageEnglish
Pages (from-to)318-332
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2833
Publication statusPublished - 1 Dec 2003

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P., Oct 2017, In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Contribution to journalArticle

Related by journal

  1. Multi-cue facial feature detection and tracking

    Chen, J. & Tiddeman, B., 2008, In : Lecture Notes in Computer Science. 5099 LNCS, p. 356-367 12 p.

    Research output: Contribution to journalArticle

ID: 258372514

Top