论文标题
基于图的集合涵盖问题的基于神经预测的基于神经预测的加速算法
The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problems
论文作者
论文摘要
设定覆盖问题是一类重要的组合优化问题，在许多领域都广泛应用和研究了。在本文中，我们提出了一种用神经预测（CG-P）的改进的列的生成算法，用于解决基于图的集合涵盖问题。我们利用基于图神经网络的神经预测模型来预测每个边缘最终解决方案中的概率。我们的CG-P算法构建了一个还原的图，该图仅包含具有较高预测概率的边缘，并且此图还原过程显着加快了解决方案过程。我们在铁路乘员计划问题上评估了CG-P算法，它的表现优于基线列的生成算法。我们为我们的CG-P算法提供了两种解决方案模式。在最佳模式下，我们可以获得具有最佳保证的解决方案，同时将时间成本降低到63.12％。在快速模式下，我们可以在仅2.91％的计算时间内获得具有7.62％最佳差距的亚最佳解决方案。
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.
