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
