# Column Generation with Domain-Independent Dynamic Programming

arXiv: https://arxiv.org/abs/2510.14317 · HTML: https://mlsanity.com/paper/2510.14317/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 49 references that are in the map.
- First posted on arXiv 16 Oct 2025.

## Builds on (most cited first, 2 of 2)

- [Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization](https://mlsanity.com/paper/2211.14409/) (2022)
- [Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2401.13883/) (2024)

## Abstract (arXiv)

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.