Symmetry declarations for MiniZinc

Nathaniel Baxter, Geoffrey Chu, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Symmetry is a common property of man-made systems, appearing frequently in interesting problems in research and industry. When modelling constraint satisfaction and optimisation problems, underlying symmetries can make the search for solutions or optimal solutions much harder. In contrast, when symmetries are known, they can be used to speed up solving by avoiding considering symmetric parts of the solution space. This can be achieved by using static or dynamic symmetry breaking approaches. Unfortunately symmetry breaking approaches are hard to compare. Each method is typically only implemented in one or two systems, and symmetry papers use different problems to compare and illustrate their ideas. In this paper we add symmetry declarations to the constraint modelling language MiniZinc, which is supported by a variety of solvers. These symmetries can then either be handled using static symmetry breaking constraints, or passed to a dynamic symmetry breaking method if the underlying solver supports it. The addition of symmetry declarations to a modelling language allows for specification of generic symmetries by the modeller as well as lower level handling by the solver.

Original languageEnglish
Title of host publicationACSW'16 - Proceedings of the Australasian Computer Science Week Multiconference
Subtitle of host publicationCanberra, Australia - February 01-05, 2016
EditorsDavid Parry, Peter Strazdins
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Electronic)9781450340427
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventAustralasian Computer Science Conference 2016 - Canberra, Australia
Duration: 1 Feb 20165 Feb 2016
Conference number: 39th
https://cs.anu.edu.au/conf/acsw2016/

Conference

ConferenceAustralasian Computer Science Conference 2016
Abbreviated titleACSC 2016
CountryAustralia
CityCanberra
Period1/02/165/02/16
Internet address

Keywords

  • Constraint programming
  • MiniZinc
  • Symmetry breaking

Cite this

Baxter, N., Chu, G., & Stuckey, P. J. (2016). Symmetry declarations for MiniZinc. In D. Parry, & P. Strazdins (Eds.), ACSW'16 - Proceedings of the Australasian Computer Science Week Multiconference: Canberra, Australia - February 01-05, 2016 [20] Association for Computing Machinery (ACM). https://doi.org/10.1145/2843043.2843058