{"ID":2854432,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.14317","arxiv_id":"2510.14317","title":"Column Generation Using Domain-Independent Dynamic Programming","abstract":"Column generation and branch-and-price are leading methods for large-scale exact optimization. Column generation iterates between solving a master problem and a pricing problem. The master problem is a linear program, which can be solved using a generic solver. The pricing problem is highly dependent on the application but is usually discrete. 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 prevents the reuse of components for other applications. We show that domain-independent dynamic programming, a software package for modeling and solving arbitrary dynamic programs, can be used as a generic pricing solver. We develop basic implementations of branch-and-price with pricing by domain-independent dynamic programming and show that they outperform a world-leading solver on static mixed integer programming formulations for seven problem classes.","short_abstract":"Column generation and branch-and-price are leading methods for large-scale exact optimization. Column generation iterates between solving a master problem and a pricing problem. The master problem is a linear program, which can be solved using a generic solver. The pricing problem is highly dependent on the application...","url_abs":"https://arxiv.org/abs/2510.14317","url_pdf":"https://arxiv.org/pdf/2510.14317v1","authors":"[\"Ryo Kuroiwa\",\"Edward Lam\"]","published":"2025-10-16T05:23:50Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.AI\"]","methods":"[]","has_code":false}