Set covering problem is an important class of combinatorial optimization problems, which has been widely applied and studied in many fields. In this paper, we propose an improved column generation algorithm with neural prediction (CG-P) for solving graph-based set covering problems. We leverage a graph neural network based neural prediction model to predict the probability to be included in the final solution for each edge. Our CG-P algorithm constructs a reduced graph that only contains the edges with higher predicted probability, and this graph reduction process significantly speeds up the solution process. We evaluate the CG-P algorithm on railway crew scheduling problems and it outperforms the baseline column generation algorithm. We provide two solution modes for our CG-P algorithm. In the optimal mode, we can obtain a solution with an optimality guarantee while reducing the time cost to 63.12%. In the fast mode, we can obtain a sub-optimal solution with a 7.62% optimality gap in only 2.91% computation time.
翻译:覆盖问题的设定是一个重要的组合优化问题类别, 已经在很多领域广泛应用和研究过。 在本文中, 我们建议用神经预测( CG- P) 改进柱生成算法, 解决基于图形的覆盖问题。 我们利用基于图形的神经网络预测模型来预测每个边缘的最终解决方案中包含的概率。 我们的 CG- P 算法构建了一个缩小的图表, 仅包含预测概率较高的边缘, 而这个图形减少过程大大加快了解决方案进程。 我们评估了铁路船员调度问题的 CG- P 算法, 并且超过了基线列生成算法。 我们为我们的 CG- P 算法提供了两种解决方案模式。 在最佳模式下, 我们可以获得一个解决方案, 优化性保证, 同时将时间成本降低到63.12 % 。 在快速模式下, 我们只能在2. 91% 的计算时间内获得一个7. 62% 最佳性差的亚最佳解决方案 。