Compiling conditional constraints

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

Abstract

Conditionals are a core concept in all programming languages. They are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. The behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for both constraint programming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings
EditorsThomas Schiex, Simon de Givry
Place of PublicationCham Switzerland
PublisherSpringer
Pages384-400
Number of pages17
ISBN (Electronic)9783030300487
ISBN (Print)9783030300470
DOIs
Publication statusPublished - 2019
EventInternational Conference on Principles and Practice of Constraint Programming 2019 - Stanford, Stamford, United States of America
Duration: 30 Sep 20194 Oct 2019
Conference number: 25th
https://cp2019.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11802
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2019
Abbreviated titleCP 2019
CountryUnited States of America
CityStamford
Period30/09/194/10/19
Internet address

Keywords

  • Conditional constraints
  • Constraint modelling
  • MiniZinc

Cite this

Stuckey, P. J., & Tack, G. (2019). Compiling conditional constraints. In T. Schiex, & S. de Givry (Eds.), Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings (pp. 384-400). (Lecture Notes in Computer Science ; Vol. 11802 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-30048-7_23
Stuckey, Peter J. ; Tack, Guido. / Compiling conditional constraints. Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. editor / Thomas Schiex ; Simon de Givry. Cham Switzerland : Springer, 2019. pp. 384-400 (Lecture Notes in Computer Science ).
@inproceedings{2c825874f9c94aaca32ac27e2fb717be,
title = "Compiling conditional constraints",
abstract = "Conditionals are a core concept in all programming languages. They are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. The behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for both constraint programming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.",
keywords = "Conditional constraints, Constraint modelling, MiniZinc",
author = "Stuckey, {Peter J.} and Guido Tack",
year = "2019",
doi = "10.1007/978-3-030-30048-7_23",
language = "English",
isbn = "9783030300470",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "384--400",
editor = "Thomas Schiex and {de Givry}, Simon",
booktitle = "Principles and Practice of Constraint Programming",

}

Stuckey, PJ & Tack, G 2019, Compiling conditional constraints. in T Schiex & S de Givry (eds), Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. Lecture Notes in Computer Science , vol. 11802 , Springer, Cham Switzerland, pp. 384-400, International Conference on Principles and Practice of Constraint Programming 2019, Stamford, United States of America, 30/09/19. https://doi.org/10.1007/978-3-030-30048-7_23

Compiling conditional constraints. / Stuckey, Peter J.; Tack, Guido.

Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. ed. / Thomas Schiex; Simon de Givry. Cham Switzerland : Springer, 2019. p. 384-400 (Lecture Notes in Computer Science ; Vol. 11802 ).

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

TY - GEN

T1 - Compiling conditional constraints

AU - Stuckey, Peter J.

AU - Tack, Guido

PY - 2019

Y1 - 2019

N2 - Conditionals are a core concept in all programming languages. They are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. The behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for both constraint programming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.

AB - Conditionals are a core concept in all programming languages. They are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. The behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for both constraint programming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.

KW - Conditional constraints

KW - Constraint modelling

KW - MiniZinc

UR - http://www.scopus.com/inward/record.url?scp=85075745006&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-30048-7_23

DO - 10.1007/978-3-030-30048-7_23

M3 - Conference Paper

SN - 9783030300470

T3 - Lecture Notes in Computer Science

SP - 384

EP - 400

BT - Principles and Practice of Constraint Programming

A2 - Schiex, Thomas

A2 - de Givry, Simon

PB - Springer

CY - Cham Switzerland

ER -

Stuckey PJ, Tack G. Compiling conditional constraints. In Schiex T, de Givry S, editors, Principles and Practice of Constraint Programming : 25th International Conference, CP 2019 Stamford, CT, USA, September 30 – October 4, 2019 Proceedings. Cham Switzerland: Springer. 2019. p. 384-400. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-30048-7_23