Relaxations semidéfinies pour les problèmes d'affectation de fréquences dans les réseaux mobiles et de l'affectation quadratique

Malgré le développement exponentiel de l'informatique, de nombreux problèmes ne peuvent pas être résolus de manière exacte en un temps de calcul raisonnable. Il en va ainsi des deux problèmes étudiés dans cette thèse, à savoir le problème de l'affectation de fréquences (FAP) et le problème de l'affectation quadratique (QAP).Le FAP et le QAP se modélisent par des problèmes d'optimisation quadratiques en nombres entiers. En pratique, les instances de ces problèmes comportent un nombre de contrainte et de variable très important. Il est donc irréaliste d'appliquer directement des méthodes de résolution exacte sur des instances réelles. Il est cependant intéressant de calculer des bornes inférieures de bonne qualité. Ces bornes peuvent être calculées en relâchant certaines contraintes du problème. Parmi les différentes relaxations possibles, nous mettrons l'accent sur la relaxation linéaire classique de Fortet, la relaxation RLT (Reformulation-Linearization technique) dûe aux travaux de Sherali et Adams et sur la relaxation semidéfinie (SDP). La relaxation semidéfinie est celle que nous avons étudiée de manière approfondie.Nous proposons d'amélioration des bornes inférieures SDP par l'introduction d'inégalités valides dans un algorithme de plans coupants. Ces inégalités induisent des facettes du polytope quadrique. Nous verrons à travers les résultats numériques l'intérêt de cet approche. Nous présentons aussi les heuristiques que nous avons développées pour calculer des solutions approchées du FAP afin d'évaluer la qualité denos bornes inférieures.Nous comparons également les résultats des heuristiques implémentées par France Telecom avec nos propres résultats.Despite an exponential increase of calculators processing data capacity, many problems still can not be solved in a reasonable computing time. Among these, the two problems studied in this thesis: the wireless network frequency assignment problem (FAP) and the quadratic assignment problem (QAP) which are known to be among the hardest combinatorial optimization problems.Theoretically, the FAP and QAP problems are modeled by a discrete quadratic optimization, but practically, instances of these problems involve such a large number of variables and constraints that makes it unrealistic to give an exact solution. However, it's interesting to calculate a lower bound that's leads to reduced size problems. These limits are calculated by relaxing some of the problem constraints. In this thesis we study the Fortet linear relaxation, the Reformulation-Linearization Technique RLT and we focus especially on the semidefinite relaxation (SDP).We introduce a new approach to improve systematically the SDP lower bounds by adding a set of some valid inequalities inducing facets of the quadric polytope. We report computational results that show the efficiency of this approach.We present also heuristics to calculate FAP upper bounds solutions and compare them to the lower bounds. Finally, we compare our results to those obtained by heuristics developed by France telecom.ORSAY-PARIS 11-BU Sciences (914712101) / SudocSudocFranceF