The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problems
This work addresses railway crew scheduling and similar combinatorial optimization problems, offering incremental improvements in speed and efficiency.
The paper tackles graph-based set covering problems by proposing an improved column generation algorithm with neural prediction (CG-P), which uses a graph neural network to predict edge probabilities and reduces the graph to speed up solving. It achieves a 63.12% time reduction with optimality guarantee and a 2.91% computation time with a 7.62% optimality gap in railway crew scheduling.
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.