Modelling dynamic programming-based global constraints in constraint programming

Andrea Visentin, Steven Prestwich, Roberto Rossi, Armagan Tarim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationOptimization of Complex Systems
Subtitle of host publicationTheory, Models, Algorithms and Applications
EditorsHoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
PublisherSpringer
Pages417-427
Number of pages11
ISBN (Electronic)9783030218034
ISBN (Print)9783030218027
DOIs
Publication statusPublished - 19 Jun 2019
Event6th 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

NameAdvances in Intelligent Systems and Computing
PublisherSpringer-Verlag
Volume991
Name
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365

Conference

Conference6th World Congress on Global Optimization
Abbreviated titleWCGO 2019
CountryFrance
CityMetz
Period8/07/19 → …
Internet address

Keywords

  • constraint programming
  • dynamic programming
  • MIP
  • encoding

Fingerprint Dive into the research topics of 'Modelling dynamic programming-based global constraints in constraint programming'. Together they form a unique fingerprint.

Cite this