FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program

• DOI: 10.1609/aaai.v39i11.33222
• Publication Date: 2025-04-11T12:01:37Z
• Authors: Yi-Xiang Hu; Feng Wu; Shaoang Li; Yifang Zhao; Xiang-Yang Li
• Keywords: Column generation

Column Generation (CG) is an effective and iterative algorithm to solve large-scale linear programs (LP). During each CG iteration, new columns are added improve the solution of LP. Typically, greedily selects one column with most negative reduced cost, which can be improved by adding more at once. However, selecting all costs would lead addition redundant that do not objective value. Therefore, appropriate add still open problem previous machine-learning-based approaches for only a constant quantity per iteration due state-space explosion problem. To address this, we propose Fast Family (FFCG) — novel reinforcement-learning-based variable number as needed in iteration. Specifically, formulate selection MDP design reward metric balances both convergence speed columns. In our experiments, FFCG converges faster on common benchmarks reduces iterations 77.1% Cutting Stock Problem (CSP) 84.8% Vehicle Routing Time Windows (VRPTW), 71.4% reduction computing time CSP 84.0% VRPTW average compared several state-of-the-art baselines.