2006 Journée d'Automne

Date : Vendredi 27 octobre 2006

Lieu : Institut Henri-Poincaré

Participants: plus de 80 personnes

Lien : http://lmi2.insa-rouen.fr/jor/programme.html

Programme de la première journée

9h00 Accueil

9h30-10h30 Adam Ouorou France Telecom Division R&D

Optimisation robuste pour le dimensionnement des réseaux de télécommunications

Dans les télécommunications, la demande est un paramètre important régissant la plannification des réseaux. Dans ce marché fortement concurrentiel, la demande présente une variabilité considérable due aux mouvements des clients et l'introduction de nouveaux services et produits. Les données historiques pour prédire le futur sont caduques car le domaine change continuellement et pour de nouveaux services, elles ne sont même pas disponibles. L'optimisation de réseaux avec une seule matrice de trafic devient inappropriée. Il devient important de tenir compte de l'incertitude des paramètres réseaux dès le début de la plannification. C'est dans ce contexte que nous considérons le problème d'affectation des capacités avec prise en compte du problème d'incertitude qui caractérise la demande dans le cadre de l'optimisation robuste. Nous proposons plusieurs modèles et présenterons des méthodes de résolution.

11h00-12h00 Ali Ridha Mahjoub

Professeur Université Blaise Pascal Clermont 2

Conception de Réseaux avec Contraintes de Bornes

Nous discutons de certains problèmes de conception de réseaux avec contraintes de bornes. Ces problèmes ont des applications dans le domaine de télécommunications. Nous considérons en particulier les deux variantes du problème du sous graphe 2-arête connexe avec des cycles bornés et des chaînes bornées. Nous présentons certains résultats liés à la structure polyèdrale de ces problèmes ainsi des algorithmes de coupes et branchements utilisant ces résultas. Nous discutons également de la complexité de certains cas particuliers de ces problèmes.

13h30-14h30 Martine Labbé

Professeur Université Libre de Bruxelles

Bilevel programming and network pricing problems

Consider a general taxation model involving two levels of decision-making. The upper level (leader) imposes taxes on a specified set of goods or services while the lower level (follower) optimizes its own objective function, taking into account the taxation scheme devised by the leader. This model belongs to the class of bilevel optimization problems where both objective functions are bilinear. In this talk, we review this class of hierarchical problems from both theoretical and algorithmic points of view.

We first introduce a general taxation model and present some of its properties. Then, we focus on the problem of setting tolls on a specified subset of arcs of a multicommodity transportation network. In this context the leader corresponds to the profit-maximizing owner of the network, and the follower to users travelling between nodes of the network. The users are assigned to shortest paths with respect to a generalized cost equal to the sum of the actual prices for using specific arcs plus routing costs. Among others, we present complexity results, identify some polynomial cases and propose mixed integer linear formulations for that network pricing problem.

This talk is an overview of joint works with Luce Brotcorne, Sophie Dewez, Géraldine Heilporn, Patrice Marcotte and Gilles Savard.

14h30-15h10 Michel Minoux

Professeur UPMC-Paris 6

Optimisation bi-niveau: vue d'ensemble des méthodes et application à des problèmes de réseaux

La problématique de l'optimisation bi-niveau apparait dans de nombreuses

applications, par exemple dans les domaines des réseaux de transport ou de télécommunications. Nous présentons une introduction aux modèles et aux méthodes de résolution, puis une application récente aux télécommunications ayant motivé une approche nouvelle afin de surmonter les difficultés dues à la grande taille du modèle bi-niveau à résoudre.

15h40-16h40 Jean-François Maurras

Professeur Université de la Méditerranée Une élégante famille de polyèdres

Soit E un ensemble fini et H une famille de parties de E telle que deux membres de cette famille diffèrent au moins de deux éléments de E. Soit F le complémentaire de H par rapport à P(E), l'ensemble des parties de E. Dans cet exposé nous caractériserons l'enveloppe convexe des vecteurs caractéristiques des parties contenues dans F. Nous considèrerons aussi le polaire de ce polyèdre et nous étudierons ses liens avec certains polyèdres connus, celui du voyageur de commerce notamment.