A generic method for identifying and exploiting dominance relations

Geoffrey Chu, Peter J. Stuckey

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

6 Citations (Scopus)

Abstract

Many constraint problems exhibit dominance relations which can be exploited for dramatic reductions in search space. Dominance relations are a generalization of symmetry and conditional symmetry. However, unlike symmetry breaking which is relatively well studied, dominance breaking techniques are not very well understood and are not commonly applied. In this paper, we present formal definitions of dominance breaking, and a generic method for identifying and exploiting dominance relations via dominance breaking constraints. We also give a generic proof of the correctness and compatibility of symmetry breaking constraints, conditional symmetry breaking constraints and dominance breaking constraints.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings
PublisherSpringer
Pages6-22
Number of pages17
ISBN (Print)9783642335570
DOIs
Publication statusPublished - 7 Nov 2012
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2012 - Quebec, Canada
Duration: 8 Oct 201212 Oct 2012
Conference number: 18th
http://archive.a4cp.org/cp2012/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7514 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2012
Abbreviated titleCP 2012
CountryCanada
CityQuebec
Period8/10/1212/10/12
Internet address

Cite this