Half reification and flattening

Thibaut Feydy, Zoltan Somogyi, Peter J. Stuckey

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

18 Citations (Scopus)

Abstract

Usually propagation-based constraint solvers construct a constraint network as a conjunction of constraints. They provide propagators for each form of constraint c. In order to increase expressiveness, systems also usually provide propagators for reified forms of constraints. A reified constraint b ↔ c associates a truth value b with a constraint c. With reified propagators, systems can express complex combinations of constraints using disjunction, implication and negation by flattening. In this paper we argue that reified constraints should be replaced by half-reified constraints of the form b → c. Half-reified constraints do not impose any extra burden on the implementers of propagators compared to unreified constraints, they can implement reified propagators without loss of propagation strength (assuming c is negatable), they extend automatically to global constraints, they simplify the handling of partial functions, and can allow flattening to give better propagation behavior.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming, CP 2011 - 17th International Conference, Proceedings
PublisherSpringer
Pages286-301
Number of pages16
ISBN (Print)9783642237850
DOIs
Publication statusPublished - 26 Sep 2011
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2011 - Perugia, Italy
Duration: 12 Sep 201116 Sep 2011
Conference number: 17th
http://www.dmi.unipg.it/cp2011/

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2011
Abbreviated titleCP 2011
CountryItaly
CityPerugia
Period12/09/1116/09/11
Internet address

Cite this

Feydy, T., Somogyi, Z., & Stuckey, P. J. (2011). Half reification and flattening. In Principles and Practice of Constraint Programming, CP 2011 - 17th International Conference, Proceedings (pp. 286-301). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6876 LNCS). Springer. https://doi.org/10.1007/978-3-642-23786-7_23