DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.26

GRID: Graph-Based Modelling Interface for Domain-Independent Dynamic Programming

Authors: Fabio Giordana, Zeynep Kiziltan, and Ryo Kuroiwa

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Domain-Independent Dynamic Programming (DIDP) is a general framework for solving combinatorial optimization problems using Dynamic Programming (DP), where search is separated from the problem specification. However, modelling directly in DIDP requires defining state variables, transitions, and dominance relations, which can be complex and error-prone. We introduce GRID, a modelling interface that enables high-level DP-oriented specifications. Users describe entities, relations, and resource attributes over a graph-based structure, from which GRID automatically compiles a DIDP model by deriving the components required by a DIDP solver. Common modelling elements are supported with built-in semantics, while additional constraints can be specified through user-defined variables and expressions. We use vehicle routing problems as a case study to present GRID and evaluate it on three variants: CVRP, PDPTW, and ECVRP. Results show that compilation overhead from GRID to DIDP is small and that generated models remain competitive with manually designed DIDP models while outperforming state-of-the-art CP and mixed-integer programming approaches.

Cite as

Fabio Giordana, Zeynep Kiziltan, and Ryo Kuroiwa. GRID: Graph-Based Modelling Interface for Domain-Independent Dynamic Programming. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{giordana_et_al:LIPIcs.CP.2026.26,
  author =	{Giordana, Fabio and Kiziltan, Zeynep and Kuroiwa, Ryo},
  title =	{{GRID: Graph-Based Modelling Interface for Domain-Independent Dynamic Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{26:1--26:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.26},
  URN =		{urn:nbn:de:0030-drops-266584},
  doi =		{10.4230/LIPIcs.CP.2026.26},
  annote =	{Keywords: Modelling \& Modelling Languages, Dynamic Programming}
}

Search Results

Documents authored by Giordana, Fabio

GRID: Graph-Based Modelling Interface for Domain-Independent Dynamic Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message