Abstract : Plusieurs résultats spectaculaires dans le domaine de l’approximation polynomiale ont popularisé l’approche par programmation semidéfinie (PSD) dans la communauté de l’optimisation combinatoire. Avec le développement d’outils de résolution numérique de plus en plus efficaces et l’établissement d’un cadre théorique et de modèles spécifiques à l’optimisation combinatoire, la PSD suscite un intérêt croissant tant pour la résolution approchée qu’exacte de problèmes difficiles. Dans cet exposé, nous introduirons les notions essentielles pour mettre en oeuvre efficacement la PSD : éléments de base, relaxations, liens avec les autres approches, spectre d’application et limites. Plusieurs problèmes traités par PSD et résultats récents illustreront les démarches présentées.

Abstract : We consider the Frequency Assignment Problem (FAP) in the case when the important components of problem formulation are uncertain and can be modelled by random variables. In particular, we look at the case when the interference between sources and/or demand for frequences have random nature. Several optimization models which belong to stochastic programming approach are considered. Solution schemes based on semi-definite relaxations are developed. Presented results including numerical experiments confirm that stochastic programming modeling tools coupled with semi-definite relaxations constitute a promising approach for solving frequency assignment problems under uncertainty.

Abstract : Tout d’abord, nous montrerons comment la SDP synthétise une large classe de problèmes de type réseau et embrasse les questions de minimisation du délai moyen des paquets, ou encore les notions d’équité. Ensuite, nous aborderons le domaine radio et nous montrerons en quoi la SDP permet de formuler des questions importantes de capacité, et les liens avec la racine de Perron d’une matrice. Enfin, nous nous plongerons dans le monde du web, et par inspiration de la célèbre résolution du problème de Max-Cut par l’algorithme de Goemans-Williamson, nous montrerons comment il est possible de présenter de manière originale un ensemble très large de documents liés entre eux.

Abstract : On s’intéresse à la résolution exacte de problèmes d’optimisation en variables 0-1 comportant une fonction objectif quadratique soumise à des contraintes linéaires. Ces problèmes sont généralement non convexes. Plus précisément, leur relaxation continue n’est pas un problème convexe. Pour pallier cette difficulté, l’approche principale présentée consiste en une reformulation quadratique convexe du problème initial. Cette nouvelle méthode met en jeu la programmation semidéfinie, aussi bien sur le plan théorique que pratique.