Décomposition de Dantzig-Wolfe et décomposition simpliciale en programmation quadratique

Session : SS12 / SS12 : Programmation non-linéaire en variables mixtes entières
Jeudi 11 février 15:00 - 16:40 Salle : CI2-07
Lucas Létocart, Enrico Bettiol, Alberto Ceselli, Francesco Rinaldi et Emiliano Traversi

La programmation quadratique consiste à résoudre des problèmes dans lesquels on optimise une fonction quadratique soumise à des contraintes quadratiques et/ou linéaires. Nous nous intéressons ici aux problèmes avec objectif quadratique, contraintes linéaires et variables continues ou binaires. Dans un premier temps nous montrerons comment résoudre le problème du sac à dos quadratique avec contrainte de cardinalité en utilisant la décomposition de Dantzig-Wolfe et dans un second temps, nous utiliserons la décomposition simpliciale pour résoudre le problème d’optimisation de portefeuille et nous montrerons le lien avec la décomposition de Dantzig-Wolfe.

Mots clés : Décomposition de Dantzig-Wolfe, Décomposition simpliciale, Programmation quadratique