Franklin Djeumou Fomeni, PhD

Binary Quadratic Programs (BQP)

A vast array of important problems can be formulated as binary quadratic optimization (BQO) problem. This includes, for example, portfolio optimization, project selection, facilities layout, VLSI design, etc. At present, the most successful approaches to solving BQO to proven optimality use either linear programming (LP) or semi-definite programming (SDP) relaxations. The LP-based algorithms, and to some extent also the SDP-based ones, can benefit from the addition of strong valid linear inequalities, a.k.a. cutting planes. One focus of my research in this area is to find new families of cutting planes, and to develop efficient separation algorithms for both these news inequalities and the existing ones.

On the other hand, one of the most studied variant of BQO is the quadratic knapsack problem (QKP). The state-of-the-art algorithm for solving the QKP to optimality uses a Lagrangian decomposition approach, but is limited with the size of the problems that can be solved. I have developed a very effective deterministic heuristic algorithm based on dynamic programming which can solve significantly larger QKP instances. I also discovered new families of cutting planes to this problem which has been used to develop a cut-and-branch algorithm for the QKP. The latter work is in progress to implement a full branch-and-cut algorithm, which is expected to outperform the state-of-the-art QKP algorithm by a large margin.