T3Mermaid to ASCII art (mermaid-ascii)T3Kimi K3, and what we can still learn from the pelican benchmarkT3Firefox in WebAssemblyT3Spot birds not golfT3[AINews] Kimi K3 2.8T-A50B: the largest open model ever released; Opus 4.8-class at Sonnet 5 pricingT1From physical surfaces to human-centric heat stress: LST and UTCI heat mapping reveals nonlinear effects of urban morphologyT1DualHNIE: Dual-Channel Hypergraph Learning for Node Importance Estimation in Heterogeneous Knowledge GraphsT1GenTL: A General Transfer Learning Model for Building Thermal DynamicsT1A short review on the maximum clique problem algorithms with classical, AI, and quantum methodsT1Man, Machine, and Masterpiece: Artistic Ownership in the AI EraT1HABIB_TAZ at SemEval-2026 Task 11: Disentangling Formal Logic from Content via Synthetic Training and Multi-Objective OptimizationT1How Well Does AI-Generated Feedback Work? Intrinsic and Extrinsic Evaluation across more than 20,000 EFL Essay DraftsT3Mermaid to ASCII art (mermaid-ascii)T3Kimi K3, and what we can still learn from the pelican benchmarkT3Firefox in WebAssemblyT3Spot birds not golfT3[AINews] Kimi K3 2.8T-A50B: the largest open model ever released; Opus 4.8-class at Sonnet 5 pricingT1From physical surfaces to human-centric heat stress: LST and UTCI heat mapping reveals nonlinear effects of urban morphologyT1DualHNIE: Dual-Channel Hypergraph Learning for Node Importance Estimation in Heterogeneous Knowledge GraphsT1GenTL: A General Transfer Learning Model for Building Thermal DynamicsT1A short review on the maximum clique problem algorithms with classical, AI, and quantum methodsT1Man, Machine, and Masterpiece: Artistic Ownership in the AI EraT1HABIB_TAZ at SemEval-2026 Task 11: Disentangling Formal Logic from Content via Synthetic Training and Multi-Objective OptimizationT1How Well Does AI-Generated Feedback Work? Intrinsic and Extrinsic Evaluation across more than 20,000 EFL Essay Drafts

Column Generation with Domain-Independent Dynamic Programming

Primary research

#417

T1digested

Canonical URL: http://arxiv.org/abs/2510.14317v2
Topic: Systems and Efficiency
First seen: 2026-07-16 23:33:03
Last seen: 2026-07-16 23:33:03

Source raw items (1)

arXiv2026-07-16 23:32:00
Column Generation with Domain-Independent Dynamic Programming
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.