Groupe d’études et de recherche en analyse des décisions

Recent algorithmic advances for the quadratic knapsack problem

Franklin Djeumou Fomeni Professeur adjoint, Département d'analytique, opérations et technologies de l'information, Université du Québec à Montréal, Canada

Franklin Djeumou Fomeni

Présentation sur YouTube

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)