Column generation is a widely adopted technique for solving linear programming problems with a large number of variables. However, standard column generation often suffers from slow convergence due to the dual solution instability. In this paper, we present a novel learning-based stabilization approach for column generation. Unlike traditional methods that address dual solution stabilization at each iteration in isolation, our method adopts a holistic perspective, leveraging its learning-based nature to explore for optimal stabilization policies that lead to faster overall convergence. We frame dual solution stabilization as a sequential decision-making problem and cast column generation as a Markov decision process. A graph convolutional neural network-based agent is employed to improve dual solution quality at each iteration. Additionally, we introduce a two-stage training scheme that combines supervised learning and reinforcement learning, ensuring stable and efficient training of the agent. Experimental evaluations on cutting stock and vertex coloring problems demonstrate that our approach outperforms several well-known stabilization methods in terms of iteration efficiency and exhibits competitive performance in terms of total runtime. Furthermore, our method shows strong generalization capabilities, performing well on significantly larger problem instances and diverse benchmarks.

Column generation (CG) is one of the most successful approaches for solving large-scale linear programming (LP) problems. Given an LP with a prohibitively large number of variables (i.e., columns), the idea of CG is to explicitly consider only a subset of columns and iteratively add potential columns to improve the objective value. While adding the column with the most negative reduced cost can guarantee the convergence of CG, it has been shown that adding multiple columns per iteration rather than a single column can lead to faster convergence. However, it remains a challenge to design a multiple-column selection strategy to select the most promising columns from a large number of candidate columns. In this paper, we propose a novel reinforcement-learning-based (RL) multiple-column selection strategy. To the best of our knowledge, it is the first RL-based multiple-column selection strategy for CG. The effectiveness of our approach is evaluated on two sets of problems: the cutting stock problem and the graph coloring problem. Compared to several widely used single-column and multiple-column selection strategies, our RL-based multiple-column selection strategy leads to faster convergence and achieves remarkable reductions in the number of CG iterations and runtime.

The column generation (CG) algorithm is widely used in large-scale optimization problems. However, a large amount of columns in the restricted master problem (RMP) makes the computing process very time-consuming. This paper proposes a machine learning based column elimination strategy to accelerate the CG algorithm. Our approach represents the RMP by a bipartite graph and applies a learned Graph Neural Network model to predict redundant columns to be eliminated from the RMP, so as to reduce the time cost of solving the RMP and iterations required for convergence. Our approach is tested on cutting stock problem instances. Compared with the vanilla CG algorithm, the iterations and time required for convergence are reduced by up to 31 % and 48%, respectively. Furthermore, our approach shows great generalization to cutting stock problem instances of different sizes.