15/06/07 : Programmation semi-définie

Université Pierre et Marie Curie (Paris 6)
Amphi Chouard - Tour 53
4, place Jussieu
75005 Paris

Pour s’incrire : envoyer un mail à journeeJFRO@gmail.com
en indiquant vos coordonnées et votre organisme

Programme prévisionnel

9h30-10h	Accueil des participants
10h-12h	Programmation Semidéfinie en Optimisation Combinatoire Frédéric Roupin - IIE d’Evry et Laboratoire CEDRIC du CNAM Transparents de l’exposé au format PDF 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.
12h-14h00	DEJEUNER
14h00-14h45	Stochastic Frequency Assignment Problem Using SDP relaxations Abdel Lisser - Universite Paris XI Transparents de l’exposé au format PDF 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.
14h50-15h35	Quelques succès de la SDP dans le monde des télécoms Jérôme Galtier - Inria - France Telecom Transparents de l’exposé au format PDF 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.
15h35-15h50	PAUSE
15h50-16h35	Utilisation de la programmation semidéfinie pour la résolution exacte des programmes quadratiques en variables 0-1 Marie-Christine Plateau - CNAM Transparents de l’exposé au format PDF 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.