Modelling dynamic programming-based global constraints in constraint programming

Andrea Visentin; Steven Prestwich; Roberto Rossi; Armagan Tarim

doi:10.1007/978-3-030-21803-4_42

Modelling dynamic programming-based global constraints in constraint programming

Andrea Visentin, Steven Prestwich, Roberto Rossi, Armagan Tarim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

Dynamic Programming (DP) can solve many complex problems in polynomial or pseudo-polynomial time, and it is widely used in Constraint Programming (CP) to implement powerful global constraints. Implementing such constraints is a nontrivial task beyond the capability of most CP users, who must rely on their CP solver to provide an appropriate global constraint library. This also limits the usefulness of generic CP languages, some or all of whose solvers might not provide the required constraints. A technique was recently introduced for directly modelling DP in CP, which provides a way around this problem. However, no comparison of the technique with other approaches was made, and it was missing a clear formalisation. In this paper we formalise the approach and compare it with existing techniques on MiniZinc benchmark problems, including the flow formulation of DP in Integer Programming. We further show how it can be improved by state reduction methods.

Original language	English
Title of host publication	Optimization of Complex Systems
Subtitle of host publication	Theory, Models, Algorithms and Applications
Editors	Hoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
Publisher	Springer
Pages	417-427
Number of pages	11
ISBN (Electronic)	9783030218034
ISBN (Print)	9783030218027
DOIs	https://doi.org/10.1007/978-3-030-21803-4_42
Publication status	Published - 19 Jun 2019
Event	6th World Congress on Global Optimization - Computer Science and Applications Department, LGIPM, University of Lorraine., Metz, France Duration: 8 Jul 2019 → … Conference number: 6 https://wcgo2019.event.univ-lorraine.fr/

Publication series

Name	Advances in Intelligent Systems and Computing
Publisher	Springer-Verlag
Volume	991

Name
ISSN (Print)	2194-5357
ISSN (Electronic)	2194-5365

Conference

Conference	6th World Congress on Global Optimization
Abbreviated title	WCGO 2019
Country/Territory	France
City	Metz
Period	8/07/19 → …
Internet address	https://wcgo2019.event.univ-lorraine.fr/

Keywords / Materials (for Non-textual outputs)

constraint programming
dynamic programming
MIP
encoding

Access to Document

10.1007/978-3-030-21803-4_42

VisentinEtalWCGO2019ModellingDynamicProgramming-BasedGlobalConstraints
This is a post-peer-review, pre-copyedited version of a chapter published in: Optimization of Complex Systems: Theory, Models, Algorithms and Applications. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-21803-4_42
Accepted author manuscript, 397 KB

https://link.springer.com/chapter/10.1007/978-3-030-21803-4_42

Cite this

Visentin, A., Prestwich, S., Rossi, R., & Tarim, A. (2019). Modelling dynamic programming-based global constraints in constraint programming. In H. A. L. Thi, H. M. Le, & T. P. Dinh (Eds.), Optimization of Complex Systems: Theory, Models, Algorithms and Applications (pp. 417-427). (Advances in Intelligent Systems and Computing; Vol. 991). Springer. https://doi.org/10.1007/978-3-030-21803-4_42

@inproceedings{b102fc232a0745fbaa72af26c774e159,

title = "Modelling dynamic programming-based global constraints in constraint programming",

abstract = "Dynamic Programming (DP) can solve many complex problems in polynomial or pseudo-polynomial time, and it is widely used in Constraint Programming (CP) to implement powerful global constraints. Implementing such constraints is a nontrivial task beyond the capability of most CP users, who must rely on their CP solver to provide an appropriate global constraint library. This also limits the usefulness of generic CP languages, some or all of whose solvers might not provide the required constraints. A technique was recently introduced for directly modelling DP in CP, which provides a way around this problem. However, no comparison of the technique with other approaches was made, and it was missing a clear formalisation. In this paper we formalise the approach and compare it with existing techniques on MiniZinc benchmark problems, including the flow formulation of DP in Integer Programming. We further show how it can be improved by state reduction methods.",

keywords = "constraint programming, dynamic programming, MIP, encoding",

author = "Andrea Visentin and Steven Prestwich and Roberto Rossi and Armagan Tarim",

year = "2019",

month = jun,

day = "19",

doi = "10.1007/978-3-030-21803-4_42",

language = "English",

isbn = "9783030218027",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer",

pages = "417--427",

editor = "Thi, {Hoai An Le} and Le, {Hoai Minh} and Dinh, {Tao Pham}",

booktitle = "Optimization of Complex Systems",

address = "United Kingdom",

note = "6th World Congress on Global Optimization, WCGO 2019 ; Conference date: 08-07-2019",

url = "https://wcgo2019.event.univ-lorraine.fr/",

}

Visentin, A, Prestwich, S, Rossi, R & Tarim, A 2019, Modelling dynamic programming-based global constraints in constraint programming. in HAL Thi, HM Le & TP Dinh (eds), Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Advances in Intelligent Systems and Computing, vol. 991, Springer, pp. 417-427, 6th World Congress on Global Optimization, Metz, France, 8/07/19. https://doi.org/10.1007/978-3-030-21803-4_42

Modelling dynamic programming-based global constraints in constraint programming. / Visentin, Andrea; Prestwich, Steven; Rossi, Roberto et al.
Optimization of Complex Systems: Theory, Models, Algorithms and Applications. ed. / Hoai An Le Thi; Hoai Minh Le; Tao Pham Dinh. Springer, 2019. p. 417-427 (Advances in Intelligent Systems and Computing; Vol. 991).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Modelling dynamic programming-based global constraints in constraint programming

AU - Visentin, Andrea

AU - Prestwich, Steven

AU - Rossi, Roberto

AU - Tarim, Armagan

N1 - Conference code: 6

PY - 2019/6/19

Y1 - 2019/6/19

N2 - Dynamic Programming (DP) can solve many complex problems in polynomial or pseudo-polynomial time, and it is widely used in Constraint Programming (CP) to implement powerful global constraints. Implementing such constraints is a nontrivial task beyond the capability of most CP users, who must rely on their CP solver to provide an appropriate global constraint library. This also limits the usefulness of generic CP languages, some or all of whose solvers might not provide the required constraints. A technique was recently introduced for directly modelling DP in CP, which provides a way around this problem. However, no comparison of the technique with other approaches was made, and it was missing a clear formalisation. In this paper we formalise the approach and compare it with existing techniques on MiniZinc benchmark problems, including the flow formulation of DP in Integer Programming. We further show how it can be improved by state reduction methods.

AB - Dynamic Programming (DP) can solve many complex problems in polynomial or pseudo-polynomial time, and it is widely used in Constraint Programming (CP) to implement powerful global constraints. Implementing such constraints is a nontrivial task beyond the capability of most CP users, who must rely on their CP solver to provide an appropriate global constraint library. This also limits the usefulness of generic CP languages, some or all of whose solvers might not provide the required constraints. A technique was recently introduced for directly modelling DP in CP, which provides a way around this problem. However, no comparison of the technique with other approaches was made, and it was missing a clear formalisation. In this paper we formalise the approach and compare it with existing techniques on MiniZinc benchmark problems, including the flow formulation of DP in Integer Programming. We further show how it can be improved by state reduction methods.

KW - constraint programming

KW - dynamic programming

KW - MIP

KW - encoding

U2 - 10.1007/978-3-030-21803-4_42

DO - 10.1007/978-3-030-21803-4_42

M3 - Conference contribution

SN - 9783030218027

T3 - Advances in Intelligent Systems and Computing

SP - 417

EP - 427

BT - Optimization of Complex Systems

A2 - Thi, Hoai An Le

A2 - Le, Hoai Minh

A2 - Dinh, Tao Pham

PB - Springer

T2 - 6th World Congress on Global Optimization

Y2 - 8 July 2019

ER -

Modelling dynamic programming-based global constraints in constraint programming

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this