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

A quadratic assignment solver by graph pointer networks and reinforcement learning

X. Li, C. Han, T. GUO

Lagrangian heuristics for the Quadratic Multiple Knapsack Problem

L. Galli, S. Martello, C. Rey, P. Toth