Titre : The quadratic knapsack problem and related problems

Conférencier : Franklin Djeumou Fomeni GERAD,Canada

Résumé :

The Quadratic Knapsack Problem (QKP) is a particular kind of optimization problem that was introduced in 1980 and can model a vast array of important practical problems. Its applications include portfolio optimisation, project selection, facilities location, etc. It can also appear as a sub-problem when solving other important optimization problems. Essentially, it amounts to maximizing a quadratic function of a set of binary variables, subject to a single linear constraint. An intriguing fact about the QKP is that it has both non-linear and discrete aspects. For this reason, it can be tackled in a variety of ways, for example using linear, quadratic or semidefinite programming, or Lagrangian relaxation or decomposition. At present the most competitive exact solution method for the QKP is only capable of solving instances with up 400 variables. When this method is combined with some aggressive reduction procedure, it can solve large instances. In this talk, we present an alternative solution methods for the QKP (a cut-and-branch framework). This method combines an effective heuristic method based on dynamic programming and a sophisticated cutting plane algorithm. We also present a new class of cutting planes for any mixed 0-1 polynomial program. These inequalities can be used to strengthen a given level of RLT relaxation and can be separated in polynomial time.

Entrée gratuite.

Bienvenus à tous!