Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring

• DOI: 10.48550/arxiv.2112.04906
• Publication Date: 2022-06-28
• Authors: Shen, Yunzhuang; Sun, Yuan; Li, Xiaodong; Eberhard, Andrew; Ernst, Andreas
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Artificial Intelligence (cs.AI); Computer Science - Artificial Intelligence; Optimization and Control (math.OC); FOS: Mathematics; 0211 other engineering and technologies; 02 engineering and technology; Mathematics - Optimization and Control; Machine Learning (cs.LG)

Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a subproblem with a subset of columns (i.e., variables) and gradually includes new columns that can improve the solution of the current subproblem. The new columns are generated as needed by repeatedly solving a pricing problem, which is often NP-hard and is a bottleneck of the CG approach. To tackle this, we propose a Machine-Learning-based Pricing Heuristic (MLPH) that can generate many high-quality columns efficiently. In each iteration of CG, our MLPH leverages an ML model to predict the optimal solution of the pricing problem, which is then used to guide a sampling method to efficiently generate multiple high-quality columns. Using the graph coloring problem, we empirically show that MLPH significantly enhances CG as compared to six state-of-the-art methods, and the improvement in CG can lead to substantially better performance of the branch-and-price exact method.