Towards a closer integration of dynamic programming and constraint programming

S Prestwich; Armagan Tarim; Andrea Visentin; Roberto Rossi

doi:10.29007/gscn

Towards a closer integration of dynamic programming and constraint programming

S Prestwich, Armagan Tarim, Andrea Visentin, Roberto Rossi

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

Abstract / Description of output

Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.

Original language	English
Title of host publication	GCAI-2018
Subtitle of host publication	4th Global Conference on Artificial Intelligence
Editors	Daniel Lee, Alexander Steen, Toby Walsh
Publisher	EasyChair
Pages	202-214
Volume	55
DOIs	https://doi.org/10.29007/gscn
Publication status	Published - 17 Sept 2018
Event	4th Global Conference on Artificial Intelligence (GCAI 2018) - Luxembourg, Luxembourg Duration: 17 Sept 2018 → 19 Sept 2018 https://luxlogai.uni.lu/

Publication series

Name	EPiC Series in Computing
ISSN (Print)	2398-7340

Conference

Conference	4th Global Conference on Artificial Intelligence (GCAI 2018)
Country/Territory	Luxembourg
City	Luxembourg
Period	17/09/18 → 19/09/18
Internet address	https://luxlogai.uni.lu/

Access to Document

10.29007/gscn

https://easychair.org/publications/paper/hksH

4th Global Conference on Artificial Intelligence (GCAI 2018)
Roberto Rossi (Member of programme committee)
2018
Activity: Participating in or organising an event types › Participation in conference

Cite this

@inproceedings{1aab21c6cf0649008bee009060b05698,

title = "Towards a closer integration of dynamic programming and constraint programming",

abstract = "Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.",

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

year = "2018",

month = sep,

day = "17",

doi = "10.29007/gscn",

language = "English",

volume = "55",

series = "EPiC Series in Computing",

publisher = "EasyChair",

pages = "202--214",

editor = "Daniel Lee and Alexander Steen and Toby Walsh",

booktitle = "GCAI-2018",

note = " 4th Global Conference on Artificial Intelligence (GCAI 2018) ; Conference date: 17-09-2018 Through 19-09-2018",

url = "https://luxlogai.uni.lu/",

}

Prestwich, S, Tarim, A, Visentin, A & Rossi, R 2018, Towards a closer integration of dynamic programming and constraint programming. in D Lee, A Steen & T Walsh (eds), GCAI-2018: 4th Global Conference on Artificial Intelligence. vol. 55, EPiC Series in Computing, EasyChair, pp. 202-214, 4th Global Conference on Artificial Intelligence (GCAI 2018), Luxembourg, Luxembourg, 17/09/18. https://doi.org/10.29007/gscn

Towards a closer integration of dynamic programming and constraint programming. / Prestwich, S; Tarim, Armagan; Visentin, Andrea et al.
GCAI-2018: 4th Global Conference on Artificial Intelligence. ed. / Daniel Lee; Alexander Steen; Toby Walsh. Vol. 55 EasyChair, 2018. p. 202-214 (EPiC Series in Computing).

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

TY - GEN

T1 - Towards a closer integration of dynamic programming and constraint programming

AU - Prestwich, S

AU - Tarim, Armagan

AU - Visentin, Andrea

AU - Rossi, Roberto

PY - 2018/9/17

Y1 - 2018/9/17

N2 - Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.

AB - Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.

U2 - 10.29007/gscn

DO - 10.29007/gscn

M3 - Conference contribution

VL - 55

T3 - EPiC Series in Computing

SP - 202

EP - 214

BT - GCAI-2018

A2 - Lee, Daniel

A2 - Steen, Alexander

A2 - Walsh, Toby

PB - EasyChair

T2 - 4th Global Conference on Artificial Intelligence (GCAI 2018)

Y2 - 17 September 2018 through 19 September 2018

ER -

Towards a closer integration of dynamic programming and constraint programming

Abstract / Description of output

Publication series

Conference

Access to Document

Fingerprint

Activities

4th Global Conference on Artificial Intelligence (GCAI 2018)

Cite this