An Exact Method for the Quadratic Knapsack Problem Through Binary Decision Diagram

This Mitacs Globalink project, part of a PhD thesis titled “Exact and Heuristic Methods for the Quadratic Knapsack Problem (QKP),” aims to develop new optimization techniques for solving the QKP, a problem with significant applications in industries like logistics, finance, and electronics. Building on prior successes, including a dynamic programming heuristic and an algorithm using Binary Decision Diagrams (BDDs), the project will focus on creating a branch-and-cut algorithm specifically for the QKP. This collaboration between experts from Université Laval, Université de Québec à Montréal, and Carnegie Mellon University integrates advanced BDD techniques with QKP models. The research outcomes are expected to contribute significantly to combinatorial optimization, with broad applications across various industries, enhancing global advancements in solving complex optimization challenges.

Faculty Supervisor:

Leandro Coelho;Franklin Djeumou Fomeni

Student:

Partner:

Carnegie Mellon University

Discipline:

Engineering

Sector:

Technology; Finance and Insurance; Other

University:

Université Laval

Program: