Conférenciers invités

Approximation en Optimisation multiobjectif

Cristina Bazgan

Cristina Bazgan

Université Paris Dauphine, France

Page personnelle

 

 

 

Les solutions potentiellement intéressantes pour un problème multiobjectif sont les solutions efficaces. Nous montrerons d’abord les difficultés rencontrées pour trouver l’ensemble de ces solutions. Ensuite nous présenterons les techniques et les résultats classiques existant pour approximer cet ensemble. Nous nous concentrerons sur des approximations avec une garantie a priori de la qualité de l’approximation et du temps de calcul nécessaire pour générer de telles approximations.

 

 

 

How to solve very large scale VRPs

 Kenneth Sorensen

Kenneth Sörensen

Université d’Anvers, Belgique

Page personnelle

 

 

 

We take a fresh look at the development of vehicle routing algorithms. First, we use data mining to gain knowledge on what distinguishes good solutions from « not-so-good » solutions. We then build an algorithm that is entirely based on a small set of well-chosen, complementary, and efficiently implemented local search operators and apply that knowledge to make them work effectively. Finally, the efficiency of the algorithm is improved by heavy heuristic pruning. The result is an algorithm that is both very fast and very effective, and can be scaled to solve instances that are orders of magnitude larger than those considered « large » in the literature.

 

La présentation plénière de Kenneth Sörensen est soutenue par le GT2L

 

Tutoriels du GDR-RO

 


Jeudi 22 février de 14h00 à 14h50, salle A
Algorithmes de branch-and-bound multiobjectif et vOptSolver

Xavier Gandibleux et Anthony Przybylski, Université de Nantes

Dans cet exposé, les algorithmes de résolution de problèmes d’optimisation combinatoire multiobjectif fondés sur le principe de branch-and-bound sont exposés. En particulier, les points communs entre les différentes propositions et les difficultés de mise en œuvre sont discutées. Ensuite, vOptSolver, logiciel open source de modélisation et de résolution exacte de programmes linéaires multiobjectif en variables discrètes, est présenté.

 

Jeudi 22 février de 14h00 à 14h50, salle DD
Set Partitioning Problems: Research and applications

Chengbin Chu, CentraleSupélec

In this talk, we consider set partitioning problems and their applications. We show how to formulate the problem and obtain optimal or near-optimal solutions. We present the idea of column generation and branch and price approaches to solve the problem to optimality. Especially we present the idea of aggregated state dynamic programing approach to obtain near-optimal solutions. The approaches are illustrated with applications in operating theater planning and cutting stock problems.

 


Jeudi 22 février de 14h50 à 15h40, salle A
Décision multicritère en présence d’interaction entre critères

Michel Grabisch, Université Paris I Panthéon-Sorbonne

Le tutoriel présentera une introduction générale aux problèmes de décision multicritère dans le cadre du mesurage conjoint et de la théorie de l’utilité multiattribut, et expliquera les propriétés d’indépendence préférentielle mutuelle et d’indépendance faible. On montrera comment les capacités (mesures non-additives) apparaissent naturellement dans ce cadre et comment elles permettent de représenter l’interaction entre critères. Deux extensions notables des capacités sont l’intégrale de Choquet et le modèle multilinéaire. Nous expliquerons sous quelles conditions de mesurage conjoint ces modèles peuvent exister. Enfin, nous étudierons la notion d’interaction entre critères et ses différentes définitions, et montrerons comment elles sont reliées aux modèles précédents.

 

Jeudi 22 février de 14h50 à 15h40, salle DD
Schémas d’approximation polynomiale : quand les techniques classiques deviennent incontournables

Imed Kacem, Université de Lorraine

L’objectif de ce tutoriel est de présenter les approches de construction des schémas d’approximation polynomiale pour les problèmes d’optimisation combinatoire et de mettre en évidence l’intérêt des techniques classiques (programmation dynamique, programmation linéaire, PLNE,…) dans l’élaboration de tels schémas pour certains cas difficiles. Nous présentons ces différentes approches de construction (simplification de l’instance d’entrée, modification d’un algorithme exact, structuration de l’espace des solutions). Nous présentons également des exemples d’approximation obtenues directement à l’aide de ces techniques classiques (rounding d’une relaxation linéaire, rounding d’une relaxation lagrangienne, méthode d’approximation Primal/Dual,…).

 


Jeudi 22 février de 15h40 à 16h30, salle A
Recherche opérationnelle et théorie des jeux pour l’analyse de la neutralité du Net

Bruno Tuffin, INRIA

La neutralité du Net est un sujet extrêmement sensible à travers le monde comme l’attestent les récentes décisions aux États-Unis. Au cours de cet exposé, nous introduirons les éléments du débat et décririons comment le problème peut être analysé via des outils de recherche opérationnelle, principalement la théorie des jeux. Nous étendrons également le débat à tous les acteurs de l’Internet.

 

Jeudi 22 février de 15h40 à 16h30, salle DD
Problèmes de Lot-sizing: résultats fondamentaux et applications émergentes

Safia Kedad-Sidhoum, CNAM Paris

La présentation vise à rappeler les concepts de base de la planification de production. Les modèles centraux et formulations classiques en lot-sizing seront rappelés ainsi que les méthodes dédiées pour la résolution de certaines classes de problèmes. Nous proposerons une ouverture vers des applications émergentes du domaine en particulier les problèmes avec prise en compte de contraintes environnementales et les problématiques liées à la gestion énergétique.