DROPS

Artifact

Software

Kurorororo/cp2026-cg-didp-code

Authors: Ryo Kuroiwa and Edward Lam

Abstract

Cite as

Ryo Kuroiwa, Edward Lam. Kurorororo/cp2026-cg-didp-code (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26922,
   title = {{Kurorororo/cp2026-cg-didp-code}}, 
   author = {Kuroiwa, Ryo and Lam, Edward},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:353704b294045731c53437dc128bd7ac7b9a5026;origin=https://github.com/Kurorororo/cp2026-cg-didp-code;visit=swh:1:snp:ff0b69f95012f9771b09d66c4178463f58b46d3a;anchor=swh:1:rev:689e8a6dcf4906bcc45b145f5255e11f697ad579}{\texttt{swh:1:dir:353704b294045731c53437dc128bd7ac7b9a5026}} (visited on 2026-07-13)},
   url = {https://github.com/Kurorororo/cp2026-cg-didp-code},
   doi = {10.4230/artifacts.26922},
}

Document

DOI: 10.4230/LIPIcs.CP.2026.37

Column Generation with Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and Edward Lam

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

Abstract

Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem’s structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.

Cite as

Ryo Kuroiwa and Edward Lam. Column Generation with 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. 37:1-37:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2026.37,
  author =	{Kuroiwa, Ryo and Lam, Edward},
  title =	{{Column Generation with Domain-Independent Dynamic Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{37:1--37:24},
  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.37},
  URN =		{urn:nbn:de:0030-drops-266699},
  doi =		{10.4230/LIPIcs.CP.2026.37},
  annote =	{Keywords: Modelling \& Modelling Languages, Dynamic Programming, Operations Research \& Mathematical Optimisation}
}

Document

DOI: 10.4230/LIPIcs.CP.2026.61

Constraint-Aware Self-Supervised Learning for Edge Selection

Authors: Xinda Zheng, Frits de Nijs, and Edward Lam

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

Abstract

Many edge-selection problems, such as the Traveling Salesman Problem and Orienteering Problem, are NP-hard, making them expensive to solve with exact methods and challenging to address with hand-crafted heuristics. Learning-based approaches provide an efficient alternative, while self-supervised methods avoid costly solution labels. However, existing approaches often still rely on heavy post-processing or narrow problem-specific designs. We propose a reusable self-supervised framework for edge-selection optimization that learns directly from unlabeled instances. The framework uses differentiable surrogate objectives and feasibility-driven penalties to encourage the model to learn feasibility-aware solution structure during training. To support efficient inference, we introduce a lightweight graph architecture centered on a cost-attention convolution, where edge costs and feasibility information directly shape message passing. Experiments on three problem families demonstrate strong solution quality and efficient inference across diverse edge-selection settings.

Cite as

Xinda Zheng, Frits de Nijs, and Edward Lam. Constraint-Aware Self-Supervised Learning for Edge Selection. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.CP.2026.61,
  author =	{Zheng, Xinda and de Nijs, Frits and Lam, Edward},
  title =	{{Constraint-Aware Self-Supervised Learning for Edge Selection}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{61:1--61:18},
  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.61},
  URN =		{urn:nbn:de:0030-drops-266949},
  doi =		{10.4230/LIPIcs.CP.2026.61},
  annote =	{Keywords: Combinatorial Optimization, Learning to optimize, Graph neural networks}
}

Search Results

Documents authored by Lam, Edward

Kurorororo/cp2026-cg-didp-code

Abstract

Cite as

Column Generation with Domain-Independent Dynamic Programming

Abstract

Cite as

Constraint-Aware Self-Supervised Learning for Edge Selection

Abstract

Cite as

Thanks for your feedback!

Could not send message