The Quadratic Knapsack Problem (QKP) is a well-known combinatorial optimization problem which has many applications in finance, logistics, telecommunications, facility location problems, 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. In this presentation, we will first give a broad review of the existing solution methods. Then, we will present some recent contributions in the development of solution methods for large scale QKPs. And finally, We will present some potential venues for developing even more efficient algorithms for the QKP and other related problems.
G2127.pdf (570 Ko)