Explaining alldifferent

Nicholas Downing, Thibaut Feydy, Peter J. Stuckey

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

4 Citations (Scopus)

Abstract

Lazy clause generation is a powerful approach to reducing search in constraint programming. For use in a lazy clause generation solver, global constraints must be extended to explain themselves. Alternatively they can be decomposed into simpler constraints which already have explanation capability. In this paper we examine different propagation mechanisms for the alldifferent constraint, and show how they can be extended to explain themselves. We compare the different explaining implementations of alldifferent on a variety of problems to determine how explanation changes the trade-offs for propagaton. The combination of global alldifferent propagators with explnation leads to a state-of-the-art constraint programming solution to problems involving alldifferent.

Original languageEnglish
Title of host publicationComputer Science 2012 - Proceedings of the 35th Australasian Computer Science Conference, ACSC 2012
Pages115-124
Number of pages10
Publication statusPublished - 16 Nov 2012
Externally publishedYes
EventAustralasian Computer Science Conference 2012 - Melbourne, Australia
Duration: 30 Jan 20123 Feb 2012
Conference number: 35th
https://dl.acm.org/doi/proceedings/10.5555/2483654 (Proceedings)

Publication series

NameConferences in Research and Practice in Information Technology Series
Volume122
ISSN (Print)1445-1336

Conference

ConferenceAustralasian Computer Science Conference 2012
Abbreviated titleACSC 2012
CountryAustralia
CityMelbourne
Period30/01/123/02/12
Internet address

Cite this

Downing, N., Feydy, T., & Stuckey, P. J. (2012). Explaining alldifferent. In Computer Science 2012 - Proceedings of the 35th Australasian Computer Science Conference, ACSC 2012 (pp. 115-124). (Conferences in Research and Practice in Information Technology Series; Vol. 122).