Important : Dans le cadre du plan vigipirate et afin de faciliter l’organisation de cette journée, vous devez obligatoirement vous inscrire au préalable en cliquant ici.

Quand: Le lundi 5 mars 2018
Où: En salle H218, à Télécom SudParis

Programme de la journée

– Accueil: 10h00

– 10h30-11h10- José Neto, Télécom SudParis
Titre : Approches pour le problème de coupe maximum
Résumé : Étant donné un graphe non orienté et pondéré sur les arêtes, le problème de coupe maximum consiste à déterminer un sous-ensemble de sommets S de sorte que la somme des poids des arêtes ayant exactement une extrémité dans cet ensemble soit maximum.
Différents modèles et méthodes pour aborder ce problème notoirement difficile sont présentés.

– 11h10-11h50 – Alain Faye, ENSIIE
Titre : Un algorithme quadratique pour calculer les dates d’atterrissage optimales d’une séquence d’avions
Résumé : Ce papier étudie le problème du séquencement des avions lors de leur arrivée à l’aéroport, problème connu dans la littérature sous le nom de Aircraft Landing Problem. Il s’agit de séquencer les avions arrivant sur la piste d’atterrissage tout en respectant des conditions de sécurité entre les avions. Les avions créent des turbulences et une durée minimum entre deux atterrissages successifs doit être respectée. La durée de séparation dépend du type des avions qui se suivent. Un petit avion qui atterrit derrière un gros avion doit attendre plus longtemps qu’un gros avion qui atterrit à la suite d’un petit. Chaque avion i peut atterrir dans une certaine fenêtre de temps [Ei , Li ]. Ei est la date au plus tôt à laquelle l’avion peut atterrir, Li est la date au plus tard. Dans cette fenêtre, Ti est la date préférée d’atterrissage qui correspond à la date à laquelle l’avion arriverait sur la piste s’il allait à sa vitesse de croisière. Si l’avion i était seul il atterrirait à la date Ti mais en présence d’autres avions un arbitrage est nécessaire. Les avions doivent soit accélérer pour atterrir plus tôt ou au contraire ralentir voire faire des boucles pour arriver plus tard afin de respecter les contraintes de sécurité. Une déviation par rapport à la date préférée d’atterrissage engendre un coût linéaire. L’objectif est de minimiser le coût total de déviation. Sur chaque piste, le problème se décompose en deux phases: d’abord choisir l’ordre des avions et ensuite choisir les dates d’atterrisage. Ce dernier problème peut se résoudre par un PL (Programme Linéaire). Ici nous proposons un algorithme polynomial de complexité quadratique en fonction du nombre d’avions. Cet algorithme est basé sur la programmation dynamique.
Pour tester l’efficacité de cet algorithme par rapport au PL, nous implémentons chaque méthode dans un algorithme itératif de type recuit simulé. L’algorithme itératif recherche la meilleure séquence vis-à-vis de l’objectif et le coût d’une séquence est calculé soit par le PL dans une première version de l’algorithme, soit par l’algorithme polynomial dans une deuxième version. Les deux algorithmes ont été testés sur des instances de la littérature, instances de 100 à 500 avions. L’objectif de ces tests est d’évaluer l’apport de l’algorithme polynomial par rapport au PL. Dans un premier temps, les vitesses des deux algorithmes ont été comparées.
On constate le gain important apporté par l’algorithme polynomial. L’algorithme polynomial est entre 7,8 et 9,8 fois plus rapide que le PL. Ce gain en rapidité permet à l’algorithme itératif, en un temps fixé, d’obtenir de bien meilleures solutions lorsqu’il utilise l’algorithme polynomial.

– 12h00-14h00- Pause déjeuner

-14h-14h30- Marc Castella, Télécom SudParis
Titre : Une approche d’optimisation globale pour la minimisation de critères rationnels favorisant la parcimonie
Résumé: We consider the problem of recovering an unknown signal observed through a nonlinear model and corrupted with additive noise. More precisely, the nonlinear degradation consists of a convolution followed by a nonlinear rational transform. As a prior information, the original signal is assumed to be sparse. We tackle the problem by minimizing a least-squares fit criterion penalized by a Geman-McClure like potential. In order to find a globally optimal solution to this rational minimization
problem, we transform it in a generalized moment problem, for which a hierarchy of semidefinite programming relaxations can be used. To overcome computational limitations on the number of involved variables, the structure of the problem is carefully addressed, yielding a sparse relaxation able to deal with up to several hundreds of optimized variables. Our experiments show the good performance of the proposed approach.

14h30- 15h- Gilles Geeraerts, Université Libre de Bruxelles
Titre: « To reach or not to reach? Efficient Algorithms for total payoff games »
Résumé: Quantitative games are two-player zero-sum games played on directed weighted graphs. Total-payoff games (that can be seen as a refinement of the well- studied mean-payoff games) are the variant where the payoff of a play is computed as the sum of the weights. We present the first pseudo-polynomial time algorithm for total-payoff games in the presence of arbitrary weights. It consists of a non-trivial application of the value iteration paradigm. Indeed, it requires to study, as a milestone, a refinement of these games, called min-cost reachability games, where we add a reachability objective to one of the players. For these games, we give an efficient value iteration algorithm to compute the values and optimal strategies (when they exist), that runs in pseudo-polynomial time.

– 15h00-15h15: pause

-15h15-15h45- Massinissa Merabet, Ph.D. in Computer Science, ENSIIE

Titre : Résolution du problème de recherche d’arbres couvrants ayant
un minimum de branchements
Résumé : Étant donné un graphe G = (V, E) non orienté, un sommet de G est dit sommet de branchement s’il a un degré strictement supérieur à deux. Le problème Minimum Branch Vertices (MBV) consiste à trouver un arbre couvrant de G ayant un minimum de sommets de branchement. Il trouve son intérêt pratique principalement dans le routage Broadcast appliqué aux réseaux optiques. En effet, étant le sous-graphe connexe permettant de couvrir les sommets en utilisant un minimum de liens, l’arbre est une structure classique pour ce type de routage. Dans les réseaux tout-optique, les fonctions de commutation et de routage sont fournies par les brasseurs optiques OXC (optical cross-connect). Seuls certains OXC, onéreux, peuvent diviser une longueur d’onde entrante vers plusieurs ports de sortie grâce à un coupleur optique afin d’offrir un service Broadcast. Cette division génère un affaiblissement du faisceau lumineux ainsi qu’une dégradation du signal. Un sommet de branchement dans l’arbre couvrant correspond a un sommet équipé de coupleur optique dans le réseau. Afin de réduire les coûts et de limiter les pertes, il convient donc de minimiser leur nombre, tout en garantissant la faisabilité du routage. Le problème MBV est NP-difficile et n’est pas approximable en temps polynomial avec un rapport constant. Je propose une méthode de résolution exacte utilisant la programmation linéaire en nombres entiers, un algorithme polynomial donnant une solution approchée sans garantie, ainsi qu’un noyau exponentiel de taille O(k2^k), où le paramètre k représente
le nombre de sommets dont on ne peut décider en temps polynomial s’ils sont sommets de branchement dans une solution optimale. L’existence de ce noyau démontre que ce problème est FPT vis-à-vis de k. Enfin, des expérimentations sur des graphes aléatoires permettront d’évaluer ces différentes approches.

-15h45-16h15- Remi Watrigant, Université Claude Bernard Lyon 1

Titre : Testing resiliency of instances using Integer Linear Programming

Résumé : We present a notion of resiliency for optimization or decision problems, which consists in deciding whether a solution of a given cost still exist after any (appropriately defined) modification has been applied to the instance. In order to tackle these kinds of problems, we introduce a resiliency version of an Integer Linear Program (ILP), and present a Fixed-Parameter Tractable (FPT) algorithm for testing whether an ILP is resilient. As a direct application of our approach, we study a resiliency version of a generalization of the Set Cover problem, arising in the field of access control. We analyze its parameterized complexity by considering several parameterizations, establishing the frontier between tractable and intractable cases.
This is joint work with Jason Crampton, Gregory Gutin and Martin Koutecky