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.
翻译:双级优化问题是一个与两个代理商( 领导者和追随者) 的等级优化问题。 领导者首先做出他们自己的决定, 追随者也相应地做出最佳选择。 领导者知道追随者的信息, 问题的目标是通过从领导的角度考虑追随者的反应来找到最佳解决方案。 对于双级优化问题, 没有通用和高效的算法或商业解决方案可以找到最佳解决方案, 并且即使对于一个简单的问题也很难找到一个好解决方案 。 在本文中, 我们提议了一种深层次的学习方法, 使用图形神经网络来解决双级Knappsack问题。 我们训练模型来预测领导者的解决办法, 并用它来将等级优化问题转化为单一的优化问题来找到解决方案。 我们的模式发现可行的解决方案比精确的算法要快500倍于1.7 美元 最佳差距的精确算法。 此外, 我们的模型在与它所训练的大小不同的问题上表现得很好。