Realopt

Des horaires de train à la découpe de verre : ubiquité des modèles de flots en optimisation

Résumé

1. Introduction

Ces dernières années ont vu une amélioration considérable de la puissance des solveurs génériques de programmation linéaire en nombres entiers. Ils sont aujourd'hui des outils très puissants pour résoudre des problèmes difficiles d'optimisation. Un enjeu important dans l'utilisation de ces solveurs est de trouver la bonne manière de formuler les problèmes que l'on veut résoudre. L'efficacité des algorithmes est en effet très dépendante du choix de la formulation.

2. Méthodologie

Une manière efficace de modéliser un problème est de le représenter sous la forme d'un problème de flot dans un réseau. Les modèles obtenus ont de bonnes propriétés théoriques et permettent de mettre en place des algorithmes qui leur sont dédiés. Nous illustrons ce type de modèles en montrant comment ils ont été utilisés pour résoudre des problèmes industriels dans le cadre de l'équipe RealOpt : planification de la production d'énergie, découpe de verre, emplois du temps, horaires de train, parmi d'autres.

3. Originalité / perspective

Les modèles de flot sont très faciles à mettre en place lorsque les paramètres du problème permettent de se limiter à un réseau de taille raisonnable. Un champ de recherche très important consiste à déterminer des stratégies pour obtenir des algorithmes efficaces lorsque ces paramètres sont moins favorables à l'usage direct de ces modèles.

Télécharger le résume PDF

Revoir le live :

A propos - Realopt

Decision making today relies increasingly on support from mathematical models. Quantitative modeling is routinely used in both industry and administration to design and operate transportation, distribution, or production systems. Optimization concerns every stage of the decision-making process: investment budgeting, long term planning, the management of scarce resources, or the planning of day-to-day operations. Many optimization problems that arise in decision support applications involve discrete decision variables; the resulting problems can be modeled as linear or non-linear programs with integer variables.
The solution of such problems is essentially based on enumeration techniques and can be notoriously difficult given the huge size of the solution space. A key to success is the development of better problem formulations that provide strong approximations and hence help to prune the enumerative solution scheme. One must also avoid the drawback of enumerating what are essentially symmetric solutions.
Our project aims to develop tight formulations and algorithms for combinatorial optimization problems exploiting the complementarity between the latest reformulation techniques, such as Lagrangian and polyhedral approaches (the generation of columns and cutting planes), non-linear programming tools (quadratic programming, semi-definite, and other convex relaxations), and graph theoretic tools (for induced properties and implicit representations of solutions). Our focus is on deterministic optimization approaches based on mathematical programming, but our experience extends to stochastic programming, constraint programming, and graph theory. Through industrial partnerships, the team targets large scale problems such as those arising in network design, logistic (routing problems), scheduling, cutting and packing problems, production planning and healthcare logistic.

realopt.bordeaux.inria.fr/

A propos de l'orateur