论文标题
使用图形神经网络解决双重背包问题
Solving Bilevel Knapsack Problem using Graph Neural Networks
论文作者
论文摘要
双杆优化问题是两个代理，一个领导者和一个追随者的层次优化问题。领导者首先做出自己的决定，追随者会做出最佳选择。领导者知道追随者的信息，问题的目的是通过从领导者的角度考虑追随者的反应来找到最佳解决方案。对于双重优化问题，没有一般有效的算法或商业求解器来获得最佳解决方案，即使对于一个简单的问题，也很难获得一个好的解决方案。在本文中，我们提出了一种使用图神经网络来解决二力背包问题的深度学习方法。我们训练模型以预测领导者的解决方案，并使用它将分层优化问题转换为单层优化问题以获取解决方案。我们的模型找到了可行解决方案，该解决方案的速度比$ 1.7 \％$最佳间隙的确切算法快500倍。同样，我们的模型在与训练大小不同的大小不同的问题上表现良好。
The Bilevel Optimization Problem is a hierarchical optimization problem with two agents, a leader and a follower. The leader make their own decisions first, and the followers make the best choices accordingly. The leader knows the information of the followers, and the goal of the problem is to find the optimal solution by considering the reactions of the followers from the leader's point of view. For the Bilevel Optimization Problem, there are no general and efficient algorithms or commercial solvers to get an optimal solution, and it is very difficult to get a good solution even for a simple problem. In this paper, we propose a deep learning approach using Graph Neural Networks to solve the bilevel knapsack problem. We train the model to predict the leader's solution and use it to transform the hierarchical optimization problem into a single-level optimization problem to get the solution. Our model found the feasible solution that was about 500 times faster than the exact algorithm with $1.7\%$ optimal gap. Also, our model performed well on problems of different size from the size it was trained on.
