Towards a Closer Integration of Dynamic Programming and Constraint Programming - Abstract and Dynamic Program Encoding (DPE)

Oct 4, 2026

Upload by dhado

Three connections between Dynamic Programming and Constraint Programming have been studied previously, including DP-based global constraints, memoisation during tree search, and bucket elimination. The paper introduces a new link: discrete DP algorithms can be directly encoded as constraint satisfaction problems and solved with constraint propagation, avoiding backtracking. Applications include monolithic CP models for bilevel optimisation, where filtering occurs between leader and follower variables, demonstrated on network interdiction.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

AccessFree to download

Introduction

The dynamic program encoding

DPE for Fibonacci numbers

Towards a Closer Integration of Dynamic Programming and Constraint Programming S. D. Prestwich 1 , R. Rossi2 , S. A. Tarim3 , and A. Visentin 1 1 Insight Centre for Data Analytics, University College Cork, Ireland [s.prestwich@cs.ucc.ie](s.prestwich@cs.ucc.ie),[andrea.visentin@insight-centre.org](andrea.visentin@insight-centre.org) 2 University of Edinburgh Business School, Edinburgh, UK [Roberto.Rossi@ed.ac.uk](Roberto.Rossi@ed.ac.uk) 3 Department of Management, Cankaya University, Ankara, Turkey [at@cankaya.edu.tr](at@cankaya.edu.tr) Abstract Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DPlike memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: any discrete DP algorithm 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 􀀌ltering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction. 1 Introduction Two major areas of research dealing with optimisation and decision making are Constraint Programming (CP) and Dynamic Programming (DP) . CP emerged in the 1990s from the 􀀌eld of Arti􀀌cial Intelligence. It has also been extended to Stochastic Constraint Programming (SCP) to handle problems involving uncertainty. Dynamic Programming (DP) emerged in the 1950s from the 􀀌eld of Operations Research, and is still indispensible for a wide range of modern, large-scale, deterministic and stochastic problems. CP and DP are distinct 􀀌elds with di􀀋erent techniques, applications and research communities. Like Mathematical Programming, SAT and some other problem classes, CP has languages, development tools and solvers. DP has few or none of these and is rather an approach and a collection of techniques. But unifying distinct 􀀌elds of research often leads to new insights and techniques, and it is worth looking for ways of combining CP and DP. CP/OR integrations are surveyed in [9, 10] . We know of three existing connections between the two 􀀌elds. Firstly, the DP feature of solving each subproblem once only has been emulated in CP [4] and in Constraint Logic Programming languages including Picat [21], by remembering the results of subtree searches via the technique of memoization (or tabulation) which remembers results so that they need not be recomputed. This can improve search performance by several orders of magnitude. Secondly, DP has been used to implement several e􀀎cient global constraints within CP systems [17] . Thirdly, bucket elimination [6] is a very general framework that can model DP and CP problems and others. In this paper we explore a new connection between DP and CP: by explicitly representing DP states as CP variables, we can implement a DP as a Constraint Satisfaction Problem (CSP), which we call a Dynamic Program Encoding (DPE) . A DPE is solved by constraint propagation without backtracking and can form part of a larger constraint model, allowing DP to be seamlessly integrated within CP. This includes Stochastic DP (SDP), allowing some multistage stochastic optimisation problems to be modelled as CSPs. Furthermore, replacing some constants by variables in a DPE parameterises it, leading to 􀀍exible global constraints that can be called in multiple modes, and monolithic CP models for discrete bilevel optimisation problems. The paper is organised as follows. Section 2 describes the DPE and its applications. Section 3 describes parameterised DPEs and their applications. Section 4 considers the bilevel optimisation application in detail, by modelling and solving a set of network interdiction problems. Section 5 concludes the paper and discusses future directions.

FAQs

What new connection between DP and CP does the paper propose?

It proposes a Dynamic Program Encoding (DPE) where any discrete DP algorithm is modelled and solved as a CSP using constraint propagation without backtracking.

Which prior connections between DP and CP does the paper build on?

It reviews three: DP-based global constraints, memoisation/tabulation emulating DP in CP or constraint logic programming, and bucket elimination as a unifying framework.

How does DPE work at a high level?

DPE represents each DP state as a CP variable, while seed values and recurrence relations are represented as constraints so that constraint propagation computes the values.

Oct 4, 2026

Upload by dhado