Research map / Learning theory and algorithms / Combinatorial and search optimization
FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FFCG, an RL-based family column generation that sequentially selects a variable number of columns per CG iteration using a marginal Q-value GNN agent and a reward penalizing redundant columns, reducing iterations and runtime on CSP and VRPTW.
Problem
Column generation for large-scale LPs suffers from choosing how many and which columns to add per iteration: adding all negative-reduced-cost columns creates redundancy, while fixed-count ML selection (e.g., RLMCS) is suboptimal.
Approach
Formulates multi-column selection in CG as an MDP and selects columns one at a time with a STOP action, using a marginal Q-value approximator trained with a reward that balances objective improvement against a penalty for redundant columns, reducing action space from O(2^n) to O(n^2).
Key results
- On CSP, FFCG reduces CG iterations by 77.1% and runtime by 71.4% on average versus Greedy-S.
- On VRPTW, FFCG reduces iterations by 84.8% and runtime by 84.0% versus Greedy-S (426.99 s vs 2662.07 s).
- On CSP n=50, FFCG matches Greedy-M iterations (11.81 vs 11.80) while adding far fewer columns (77.99 vs 117.97) and being faster (1.30 s vs 1.34 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FFCG instead of Greedy-S | CSP test instances · CSP | #Itr: 77.1% | Helped |
| Use FFCG instead of Greedy-S | CSP test instances · CSP | computing time: 71.4% | Helped |
| Use FFCG instead of Greedy-S | VRPTW test instances · VRPTW | #Itr: 84.8% | Helped |
| Use FFCG instead of Greedy-S | VRPTW test instances · VRPTW | computing time: 84.0% | Helped |
| Use FFCG instead of Greedy-M | CSP n=50 · CSP n=50 | #Itr: 11.80 -> 11.81 | No clear effect |
| Use FFCG instead of Greedy-M | CSP n=50 · CSP n=50 | Time (s): 1.34 -> 1.30 | Helped |
| Use FFCG instead of Greedy-M | CSP n=200 · CSP n=200 | Time (s): 2.69 -> 2.51 | Helped |
| Use FFCG instead of Greedy-M | CSP n=200 · CSP n=200 | #Itr: 35.15 -> 38.57 | Hurt |
| Use FFCG instead of Greedy-M | CSP n=750 · CSP n=750 | Time (s): 5.38 -> 4.50 | Helped |
| Use FFCG instead of Greedy-M | CSP n=750 · CSP n=750 | #Itr: 51.13 -> 56.27 | Hurt |
| Use FFCG instead of Greedy-M | CSP n=1000 · CSP n=1000 | Time (s): 11.51 -> 9.65 | Helped |
| Use FFCG instead of Greedy-M | VRPTW test instances · VRPTW | Time (s): 511.97 -> 426.99 | Helped |
Surprising findings
- Selecting all negative-reduced-cost columns (Greedy-M) yields fewer iterations on large CSP instances than FFCG (e.g., n=1000: 66.45 vs 78.86), but FFCG is faster in runtime on those instances.
Limitations
- Reward depends on hyperparameters alpha and beta that vary with problem size and require grid search.
- Sequential one-by-one selection is a local search with no optimality guarantee for the best column combination.
- Did not combine with dual stabilization or removal of non-basic columns.
Experimental setup
Datasets: BPPLIB Solomon VRPTW benchmark
Benchmarks: BPPLIB cutting stock instances (n=50,200,750,1000) Solomon VRPTW instances
Metrics: number of CG iterations total runtime (s) number of columns added objective value
Baselines: Greedy-S MLCG-S RLCG-S Greedy-M RLMCS-M RLCG
Builds on: RLCG DQN RLMCS
Closest papers by meaning
- A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation (AAAI 2024 · similarity 0.93)
- Adaptive Stabilization Based on Machine Learning for Column Generation (ICML 2024 · similarity 0.88)
- Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.84)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.84)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.83)
- MetaBox-v2: A Unified Benchmark Platform for Meta-Black-Box Optimization (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.