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


Other papers in the same session


Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.