Actualités du LIPN

Le séminaire AOC recevra le 19 juin à 12h30 Daniel Chemla (doctorant, LIPN/EPC) en B311.

Les systèmes de vélos en libre-service ont connu ces dernières années un développement sans précédent. Bien que les premières tentatives de mise en place remontent aux années 60, l’arrivée de technologies permettant un suivi des différents véhicules mis à la disposition du grand public et de l’état des bornes de stationnement en temps réel a rendu les systèmes plus sûrs. Plus de 200 villes disposent de tels dispositifs et cette tendance se poursuit avec l’entrée en fonctionnement du système de New York prévue pour l’été 2012. La mise en place d’Autolib à Paris depuis fin 2011 laisse présager l’arrivée d’un nouvel avatar de ce type de transport.

L’objectif de cette thèse de te proposer des algorithmes d’aide à la décision pour l’optimisation de réseaux de transport en libre service. L’exploitation de ces systèmes qui fleurissent actuellement un peu partout dans le monde pose en effet de nombreux problèmes, l’un des plus cruciaux étant celui de la régulation. Cette dernière a pour objectif de maintenir dans chaque station un nombre de vélos ni trop faible, ni trop élevé, afin de satisfaire au mieux la demande. Cette régulation se fait souvent par le biais de camions qui effectuent des tournées sur le réseau.

Les travaux présenté lors de ce séminaire considèrent le cas statique, où les déplacements de véhicules dûs aux usagers est considéré comme négligeable. Comment rééquilibrer le système avec un unique camion ? Et avec plusieurs camions ? Dans le premier cas, une méthode mêlant méthode tabu et branch-and-cut permet d’obtenir de bons résultats pour des instances de moins de 100 stations. Pour le cas avec plusieurs camions, une méthode de génération de colonnes est proposée, permettant de résoudre des instances de taille plus modeste, mais comparable à celle des instances résolues du Split Delivery VRP.

Le séminaire AOC recevra le 14 février à 12h30 Antonio Frangioni (professeur, Université de Pise, Italie).

We report as an unintended reformulation of a MIQP with cost-separable semi-continuous variables led us to the accidental (re)discovery of a useful concept, that of Perspective Reformulation of a MINLP, and to subsequent unexpected developments. In particular we will report of extensions to non-cost-separable variables (prompted by the need to finding another application to publish the first paper), comparison of our Semi-Infinite MILP formulation and MI-Second Order Cone formulations (prompted by the need of fending off competing teams), applications (which originally motivated the discovery) that are successful mainly for wrong reasons, as well as some more recent developments about "projected" versions of the approach, with some fresh results presented for the first time. Apart from providing an overview on a recent and potentially interesting research field in MINLP, we hope that this talk can motivate the audience to making more errors and looking at them with more interest.

Le séminaire AOC recevra le 7 novembre à 12h30 Paolo Toth (professeur, Université de Bologne, Italie).

Attention, horaire inhabituel le lundi !

The Traveling Salesman Problem (TSP) is one of the best-known combinatorial optimization and graph theory problems. In this talk, the “asymmetric” (i.e. defined on a directed graph) version of the problem, called ATSP in the following, is considered. ATSP can be defined as follows. Given a complete directed graph G, where each arc has an associated cost, a Hamiltonian circuit of G is a circuit passing through each vertex of G exactly once. The ATSP is to find a Hamiltonian circuit of G whose total cost (given by the sum of the costs of its arcs) is a minimum. Such a problem is known to be NP-hard in the strong sense, and finds many practical applications (e.g. in vehicle routing, scheduling, wiring, FMS, and sequencing problems).

The talk will review the main Integer Linear Programming formulations and the most effective exact algorithms proposed for ATSP.

Extensive computational results comparing the performance of the previously described algorithms on random and real-world instances from the literature will be reported.

Une matinée d’échange scientifique aura lieu en A303 ce mardi 11 octobre en A303.

Nous aurons d’abord une présentation/tutoriel de Sylvie Borne, suivie de deux exposés courts de Frédéric Roupin et Roland Grappe.

Le séminaire AOC recevra le 3 mai Marin Bougeret (post-doc, ENS Lyon), à 12h00 de façon exceptionnelle.

Systèmes interactifs pour la résolution de problèmes complexes : application en optimisation combinatoire, planification et ordonnancement.

Cette présentation traite de l’utilisation de l’interaction avec un oracle pour la construction d’algorithmes ayant des performances garanties.

L’oracle est considéré comme pouvant répondre instantanément et correctement à n’importe quelle question. Informellement, on s’intéresse au compromis "performance de l’algorithme, coût de l’algorithme, quantité d’information donnée par l’oracle".

Bien que l’étude de tels compromis existe dans différents domaines, tels l’algorithmique distribuée, ou l’algorithmique online, nous nous restreindrons au cadre des problèmes d’optimisation offline (avec un accent sur les problèmes d’ordonnancement), et de la théorie de l’approximation.

On s’intéresse donc au compromis "ratio d’approximation, temps d’exécution, quantité d’information donnée par l’oracle".

On souhaite écrire un algorithme interactif A_int qui, étant donné une instance, pose une question à l’oracle, et fournit grâce à la réponse une solution garantie (à un facteur ρ de l’optimal). Un tel algorithme peut ensuite être transformé en un algorithme classique A_clq (sans oracle), soit en remplaçant l’oracle par un autre algorithme B, soit en re-exécutant A_int pour toutes les réponses possibles à la question posée. Il se trouve que ce formalisme interactif a des liens forts avec des techniques usuelles de conception de schémas d’approximation.

Le premier objectif de la présentation est donc de situer ce formalisme par rapport aux techniques existantes (en examinant les possibilités qu’il offre), et de comprendre quelles sont les "bonnes" questions à poser à l’oracle pour obtenir beaucoup d’information via une "petite" réponse. Le propos sera illustré sur des exemples simples venant du problème du Knapsack, ou de l’ordonnancement de tâches indépendantes sur des machines identiques.

Le second objectif est de donner un exemple complet d’application sur le problème du "Multiple Strip Packing" (MSP). Le MSP consiste à placer des rectangles dans un nombre fixé de boîtes (ayant des largeurs différentes et des hauteurs infinies), en minimisant la hauteur maximale atteinte. Ce problème est 2-innaproximable en temps polynomial, à moins que P=NP. Je présenterai un algorithme interactif ayant un ratio d’approximation de 5/2.