Research map / Learning theory and algorithms / Combinatorial and search optimization
Adaptive Stabilization Based on Machine Learning for Column Generation
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 adaptive stabilization for column generation that uses ML (FFNN or GCN) to predict optimal dual solutions and pulls the restricted dual problem toward them with an adaptive penalty.
Problem
Column generation for large-scale linear programs suffers from heavy oscillation of dual values, slowing convergence; existing stabilization uses fixed or heuristic penalties.
Approach
Predict optimal dual variables with a machine-learned model (FFNN on statistical features of sampled maximal independent sets, or GCN) and use the prediction as a stabilization center in a generalized restricted dual problem with an adaptive penalty epsilon that is updated across iterations, retaining an optimality guarantee.
Key results
- ASCG-FFNN reaches normalized optimality gap 0.0 by iteration 80 on Matilda, versus 0.6 for SCG-Deg and 0.1 for SCG-FFNN at that point.
- On 33 GCB graphs with known optimal duals, FFNN dual prediction MSE is 0.038 versus 0.059 for GCN.
- Trained on Matilda graphs and tested on GCB graphs, showing generalization of the learned dual predictor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive stabilization with FFNN instead of SCG-FFNN | Column generation on Matilda · Matilda, Iter 20 | normalized optimality gap: 0.8 -> 0.5 | Helped |
| Use adaptive stabilization with FFNN instead of SCG-FFNN | Column generation on Matilda · Matilda, Iter 40 | normalized optimality gap: 0.5 -> 0.2 | Helped |
| Use adaptive stabilization with GCN instead of SCG-GCN | Column generation on Matilda · Matilda, Iter 20 | normalized optimality gap: 0.9 -> 0.5 | Helped |
| Use adaptive stabilization with GCN instead of SCG-GCN | Column generation on Matilda · Matilda, Iter 40 | normalized optimality gap: 0.5 -> 0.3 | Helped |
| Use FFNN rather than GCN to predict dual variables (ablation) | ASCG · GCB graphs | MSE: 0.059 -> 0.038 | Helped |
| Use a 20-layer GCN rather than a 5- or 10-layer GCN (ablation) | GCN dual prediction · Matilda | prediction result | Helped |
| Sample 5n columns rather than fewer than n columns for FFNN statistical features (ablation) | FFNN dual prediction · Graph instances | prediction accuracy | Helped |
| Increase sampled columns from 5n to 10n for FFNN statistical features (ablation) | FFNN dual prediction · Graph instances | prediction accuracy | No clear effect |
Surprising findings
- A simple FFNN on statistical features outperformed a GCN in dual prediction on GCB, although GCN was better on Matilda.
Limitations
- GCN may fail to propagate information between distant nodes that can share a column, and oversmoothing is a possible concern.
- Convergence rate improvements are not established theoretically; evaluation is empirical.
- Training relies on dual labels obtained from running classic CG on instances where optimal duals are known.
Experimental setup
Datasets: Matilda graphs GCB graphs
Benchmarks: Matilda graphs GCB graphs
Metrics: optimality gap MSE of predicted dual variables
Baselines: CG SCG SCG-Deg SCG-FFNN SCG-GCN
Builds on: column generation stabilized column generation Kraul et al. 2023 dual variable prediction
Closest papers by meaning
- A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation (AAAI 2024 · similarity 0.90)
- FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program (AAAI 2025 · similarity 0.88)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.83)
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.83)
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.82)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 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.