Stochastic quadratic knapsack problems and semidefinite programming
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
In this thesis, we study stochastic quadratic knapsack problems and applications of Semidefinite Programming for a telecommunication problem and for an experimental study of the MaxCut and CDMA problems. The first part of this thesis gives the prelimary notions and results necessary to develop and understand the contents of this thesis. The second part is the study of the stochastic quadratic knapsack problem, for which we develop a new formulation, using recourse (two-stage) and probabilistic contraints. We give multiple variants of this formulation. We propose various relaxations of this problems, based on the linear relaxation and on SDP. We show that SDP gives significantly better bounds than linear relaxation. Finally, we develop an approximation heuristic based on the result of the linear relaxation and of the second SDP relaxation, and give details of their respective performances. The third part of this thesis is dedicated to applications of SDP on pratical problems. The first application we study is a telecommunication problem : the multiuser detection problem in CDMA. We develop a new algorithm combining SDP and a VNS meta-heuristic to obtain a better signal quality. We detail the experimental results of our method and of other SDP based methods. The second application is an experimental comparison of various relaxations for the MaxCut problem and the CDMA problem. We detail the performances of Lagrangian and SDP relaxations compared to linear relaxation, and to the spectral decomposition in the CDMA case.
Abstract FR:
Dans cette thèse, nous présentons une étude détaillée de problèmes de sac-à-dos stochastiques quadratiques, ainsi que des applications de la Programmation Semidéfinie (SDP) pour un problème de télécommunications et pour une étude expérimentale pour des problèmes de Coupe Max et de CDMA. La première partie de cette thèse consiste en un rappel des notions et résultats utilisés par la suite. La seconde partie est consacrée à l’étude du problème du sac- à- dos stochastique, dont nous développons un nouveau modèle, à deux phases (recours) et à contraintes probabilistes. Nous en proposons plusieurs variantes. Nous présentons de multiples relaxations, basées sur la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin, nous proposons une heuristique d’approximation basée sur le résultat de la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin nous proposons une heuristique d’approximation, basée sur le résultat de la relaxation linéaire et sur le résultat de la seconde relaxation SDP , dont nous détaillons les performances. La troisième partie de la thèse est centrée sur l’usage de la SDP sur des problèmes pratiques. La première application étudiée est sur un problème de détection multiutilisateur dans le CDMA. Nous développons un nouvel algorithme combinant SDP et une méta-heuristique VNS pour obtenir un signal de meilleure qualité. Nous détaillons les résultats expérimentaux de notre méthode et d’autres, basées sur SDP. La seconde application est une comparaison expérimentale de diverses relaxations pour le problème de la Coupe Max et dans le CDMA. Nous présentons les performances des relaxations Lagrangienne et SDP comparées à la relaxation linéaire, ainsi que celles de la décomposition spectrale dans le cas du CDMA.