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