Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a sub-problem 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 enhancesCG 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.
翻译:专列生成( CG) 是解决大规模优化问题的有效方法。 专列生成( CG) 是解决大规模优化问题的有效方法 。 专列生成( CG) 以用一组子列( 变量) 解决子题开始, 并逐渐包括能够改善当前子题解决方案的新专列 。 新专列是根据需要反复解决定价问题产生的, 价格问题通常是NP- 硬的, 是 CG 方法的一个瓶颈 。 为了解决这个问题, 我们提议了一种基于机械学习的高压柱( MLPH ), 能够高效生成许多高品质的专列 。 在每循环一次计算 CG 时, 我们的多功能组合组合组合模型将利用一个 ML 模型来预测价格问题的最佳解决方案, 然后用来指导抽样方法, 高效生成多个高品质的专列 。 我们用图表的颜色问题, 经验显示, 专列中专列的模型与六种最新方法相比, 其改进可以极大地提高 分支和价格精确方法的性能 。