Research map / Reinforcement learning / Policy gradient and actor-critic

A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation

AAAI 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Tree search and policy optimization · 7 citations (OpenAlex)

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 an RL-based (PPO-trained actor-critic GNN) strategy for selecting multiple columns per iteration in column generation, evaluated on cutting stock and graph coloring problems.

Problem

Choosing which k columns to add per iteration in column generation so that the number of iterations and runtime are minimized, since greedy and diversity heuristics are not provably best.

Approach

Treat multi-column selection as an MDP over the RMP-candidate bipartite graph plus global features, and learn a k-combination policy with an actor-critic GNN that models candidate-column interrelations via a complete graph with GAT, trained with PPO to minimize iterations.

Key results

• On CSP (Hard), the RL strategy averages 43.95 iterations and 87.95 s versus 47.24 and 93.60 s for Diverse-M, the best baseline.
• Runtime reductions versus Diverse-M on GCP are 16.54%, 9.18%, and 6.96% across the three instance categories.
• On larger generalization instances (trained on hard CSP/GCP), the strategy still beats most baselines, e.g., CSP L=500 runtime 118.89 s vs 130.84 s for Diverse-M.

Measured effects reported in the paper

Surprising findings

• The RL strategy requires fewer iterations than the MILP expert (MILP-M) on CSP, despite MILP-M being a one-step lookahead oracle.
• The naive DQN-based top-k multiple-column variant (DQN-M) underperforms the diversification heuristic Diverse-M.

Limitations

• MILP-M and learned selection incur higher decision cost; runtime depends on GPU inference.
• Number of columns selected k is fixed (5 of 10 candidates) rather than adaptive.
• Evaluated only on two synthetic problem families (CSP and GCP).

Experimental setup

Datasets: BPPLIB-style random CSP instances random GCP graphs

Benchmarks: CSP easy/normal/hard instances GCP easy/normal/hard instances larger CSP (L=500, 1000) and GCP (N=75, 100) generalization sets

Metrics: average number of CG iterations total runtime (seconds)

Baselines: Greedy-S Random-S DQN-S Greedy-M Random-M MILP-M Diverse-M DQN-M

Builds on: PPO graph isomorphism network graph attention network DQN-based column selection (Chen et al.) CGDS diversification

Closest papers by meaning

• FFCG: Effective and Fast Family Column Generation for Solving Large-Scale Linear Program (AAAI 2025 · similarity 0.93)
• Adaptive Stabilization Based on Machine Learning for Column Generation (ICML 2024 · similarity 0.90)
• 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.83)
• Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.83)
• Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.82)