A lifted-space dynamic programming algorithm for the Quadratic Knapsack Problem
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
