Homepage
Previous JFRO
Organizing committee
Contact
18th Ile-de-France Operation Research Day
Applications de la programmation semidéfinie (SDP)
Date
This day took place
Friday, the 15 June 2007
Place
Université Pierre et Marie Curie (Paris 6) Amphi Chouard - Tour 53 4, place Jussieu 75005 Paris

Program of the day


09h30-10h00
Accueil des participants

10h00-12h00
Programmation Semidéfinie en Optimisation Combinatoire
Frédéric Roupin (IIE d’Evry et Laboratoire CEDRIC du CNAM)
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.

12h00-14h00
Déjeuner

14h00-14h45
Stochastic Frequency Assignment Problem Using SDP relaxations
Abdel Lisser (Université Paris XI)
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.

14h45-15h35
Quelques succès de la SDP dans le monde des télécoms
Jérôme Galtier (INRIA - France Telecom)
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.

15h35-15h50
Pause

15h50-16h35
Utilisation de la programmation semidéfinie pour la résolution exacte des programmes quadratiques en variables 0-1
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.

Choose language : Français English