A Framework for Solving Quadratic Knapsack Problem Based on Deep Reinforcement Learning

The quadratic knapsack problem (QKP) with constraints has been a focus of attention in combinatorial optimization, where traditional exact algorithms face difficulties in solving large-scale problems due to the problem’s NP-hard nature, and heuristic algorithms have difficulty in generating high-quality solutions in effective time. To solve QKP quickly and accurately, this paper proposes a graph pointer network (GPN) framework with hierarchical reinforcement learning (HRL). The first stage of the method trains low-level neural network to find feasible solutions that satisfy the constraint as much as possible. The second stage trains the high-level neural network based on the first stage using the objective function as a penalty term. After the HRL, our trained hierarchical GPN (HGPN) model can effectively solve the QKP. In addition, we add a greedy strategy in the decoding process to further improve the solution accuracy of the neural network solver. Experiments show that our proposed method can approximate the optimal solution produced by the Docplex solver and outperforms most end-to-end neural network solvers.