Deep learning based high accuracy heuristic approach for knapsack interdiction problem

doi:10.1016/j.cor.2024.106965

Deep learning based high accuracy heuristic approach for knapsack interdiction problem

2025-04-01

0

PRE

AI

DOI：10.1016/j.cor.2024.106965

原文链接

原文求助

摘要

En 中文

Interdiction problems area subfamily of bilevel optimization problems, characterized by a hierarchical structure involving two agents: a leader and a follower. In these problems, the objective functions of the leader and the follower are identical but are optimized in opposite directions. In this paper, we focus on the knapsack interdiction problem, where the leader and the follower compete fora shared set of items. While exact algorithms exist to solve this problem, they may not be suitable for slightly larger instances. As an alternative to exact algorithms, we propose a heuristic approach based on deep learning. Our method involves training three types of neural networks: a core network that aggregates information about the problem, a classification network that directly identifies solutions, and an identification network that assesses the reliability of the classification network's results. Our algorithm successfully finds optimal or near-optimal solutions up to 21 times faster than the exact algorithm for both the training data sizes and larger problem instances.

Keyword:

Bilevel optimization

Deep learning

Interdiction problem

Graph neural network

Heuristic

Deep learning based high accuracy heuristic approach for knapsack interdiction problem

摘要

期刊

机构