TY - GEN
T1 - Accelerating Column Generation Algorithm Using Machine-Learning-Based Column Elimination
AU - Fang, Lichang
AU - Yuan, Haofeng
AU - Zhang, Yuli
AU - Song, Shiji
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85187264481&partnerID=8YFLogxK
U2 - 10.1109/SMC53992.2023.10393948
DO - 10.1109/SMC53992.2023.10393948
M3 - Conference contribution
AN - SCOPUS:85187264481
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1945
EP - 1950
BT - 2023 IEEE International Conference on Systems, Man, and Cybernetics
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2023 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2023
Y2 - 1 October 2023 through 4 October 2023
ER -