A lifted-space dynamic programming algorithm for the Quadratic Knapsack Problem
F. Djeumou Fomeni
The Quadratic Knapsack Problem (QKP) is a well-known combinatorial optimization problem which has many applications in finance, logistics, telecommunications, etc. The QKP is NP-hard in the strong sense and the existing state-of-the-art algorithms can only handle problems of small and moderate sizes. We will present a novel heuristic algorithm for the QKP that consists of implementing the well-known dynamic programming algorithm in the space of lifted variables of the QKP. We will present some computational results which show the potentials and capabilities of this new algorithm.
Keywords: knapsack problems, integer programming, dynamic programming, local search
Scheduled
TD2 Quadratic Assignment and Knapsack Optimization
June 10, 2021 2:45 PM
2 - LV Kantorovich
Other papers in the same session
X. Li, C. Han, T. GUO
L. Galli, S. Martello, C. Rey, P. Toth
