|
Présentation
Cette UE présente les méthodes avancées et les applications
industrielles récentes en Optimisation Combinatoire et en Ordonnancement.
Elle s'intéresse à la résolution exacte des problèmes d'optimisation
combinatoire NP-difficiles (voyageur de commerce, tournées de véhicules,
coloration de graphes,...).
Elle s'appuie sur la programmation linéaire
en nombres entiers et en particulier sur les formulations contenant un
nombre exponentiel de variables et de contraintes. Ces formulations sont
résolues par différentes méthodes comme les méthodes de coupes ou les
méthodes de décomposition (relaxation lagrangienne, génération de
colonnes). Des outils théoriques comme les approches polyédrales sont
également introduits dans le but de comprendre comment l'on peut obtenir
la solution exacte d'un problème d'optimisation combinatoire de grande
dimension et comment sont conçus les solveurs d'optimisation commerciaux.
Cette UE introduit également les problématiques de l'ordonnancement
(tâches, modes d'exécution, contraintes et critères d'optimisation). La
complexité et la résolution exacte et approchée des problèmes les plus
représentatifs sont abordées. Les problèmes fondamentaux classiques
ainsi que les modèles nouveaux et non-standards seront présentés. Des
exemples applicatifs ainsi que des études de cas dans les systèmes
manufacturiers et informatiques seront développés.
Un projet sera proposé pour appréhender la pratique de la recherche opérationnelle
en partant d'une application industrielle jusqu'à sa résolution pratique.
Pour découvrir les domaines d'application de la Recherche Opérationnelle, voici une
vidéo créée la société de RO anglaise.
Organisation du module
Site officiel
Site du Master Androide
Pour trouver les salles de cours/TD et de TME:
vérifiez régulièrement le calendrier officiel
Plan du cours
- Cours 1 (18/09/19) [Pierre Fouilhoux]
- Introduction: recherche opérationnelle et optimisation combinatoire
- Rappels sur les heuristiques combinatoires
- Programmation linéaire en nombres entiers: formulations compactes et solveurs
- Techniques de modélisation: programmes non-linéaires et linéarisation
- Cours 2 (25/09/19) [Pierre Fouilhoux]
- Rappels sur Branchement et Évaluation (Branch-and-Bound)
- Points extrêmes et cas polynomiaux
- Formulations non compactes: inégalités valides et renforcement
- Cours 3 (02/10/19) [Pierre Fouilhoux]
- Méthode de coupes et branchement (Branch-and-Cut)
- TME: Algorithme Branch-and-Cut avec CPLEX
- Cours 4 (9/10/19) [Pierre Fouilhoux]
- Modélisation et Algorithmes de coupes
- TME: Algorithme Branch-and-Cut avec CPLEX (suite)
- PROJET: présentation du sujet
- Cours 5 (16/10/19) [Safia Kedad-Sidhoum]
- Lot-sizing: classification et formulations
- Problèmes polynomiaux
- PROJET: séance de suivi du projet
- Cours 6 (23/10/19) [Safia Kedad-Sidhoum]
- Inégalités valides pour le lot-sizing
- Semaine de Vacances
- Cours 7 (06/11/19) [Pierre Fouilhoux]
- Approches polyédrales
- PROJET: séance de suivi du projet
- Semaine de révision
- Examen réparti 1
- Cours 8 (27/11/19) [Pierre Fouilhoux]
- Approches polyédrales (suite)
- PROJET-TME: suivi de projet
- Cours 9 (04/12/19) [Fanny Pascual]
- Théorie de l'ordonnancement: typologie
- Problème central
- Cours 10 (11/12/19) [Fanny Pascual]
- Problèmes à une machine
- Critères réguliers et irréguliers en ordonnancement
- Cours 11 (18/12/19) [Pierre Fouilhoux]
- Relaxation et décomposition Lagrangienne (Digression hors-programme)
- Décomposition et génération de colonnes (Branch-and-Price)
- PROJET: séance de suivi du projet (date limite de fin de partie 1)
- Vacances de fin d'année
- Cours 12 (08/01/20)
- Caractérisation de polyèdres et exercices
- Ordonnancement avancé
- PROJET: séance de suivi du projet
- Cours 13 (15/01/20)
- Cours 14 (22/01/20)
- Soutenance projet
- Exercices et Révisions
TME
Plusieurs séances de TME permettent d'assimiler les notions
présentées sur des problèmes de recherche opérationnelle classiques.
TME: Heuristiques et PLNE compacte ou à nombre exponentiel de contraintes (Branch-and-Cut)
Sujet du TME: (Version du 01/10/2019)
MAOA_TP_HeurCompBac.pdf
Archive du TME: (Version du 01/10/2019)
Tutorial_CPLEX-SCIP.tgz
Dans ce module, nous étudierons comment résoudre efficacement le problème du voyageur de commerce. Cette histoire
a été mise en lumière par un film américain de Timothy Lanzone: Travelling Salesman
TME: Utilisation du logiciel PORTA pour la manipulation d'enveloppes convexes de points (entiers)
Le site du logiciel PORTA est porta.zib.de
Voir le sujet MAOA_cahier_de_tp_Porta.pdf
Projets
Un projet vise la mise en oeuvre des notions vues en cours sur un cas
concret de recherche opérationnelle (issu de la littérature).
Documents de cours et TD
Partie "Recherche Opérationnelle et Optimisation Combinatoire"
(Pierre Fouilhoux - Intervention de Cécile Rottner)
Pour impression: Le document de cours complet
TD: Cahier d'exercice
Partie "Lot-Sizing"
(Safia Kedad-Sidhoum)
Annales d'examens
Annales Janvier 2017: examMAOA-fev17.pdf
Annales Novembre 2016: examMAOA-16-nov.pdf
Annales Janvier 2016: examMAOA-janv16.pdf
Annales Novembre 2015: examMAOA-nov15.pdf
Ouvrages de références
- Combinatorial Optimization, W. Cook, W. Cunningham, W. Pulleyblank et A. Schrijver , Wiley-Interscience, 1997.
- Integer Programming, L. Wolsey, Wiley-Interscience, 1998.
- Programmation mathématiques, Michel Minoux, Lavoisier 2008.
- Approches Polyédrales en Optimisation Combinatoire, A.R. Mahjoub, Optimisation combinatoire . 1 , concepts fondamentaux, Hermes science publ. Lavoisier, 2005.
- Modèles et Algorithmes en Ordonnancement: Exercices et problèmes corrigés. Groupe GOThA. Ellipses, 2004.
- Scheduling Algorithms. Peter Brucker, Springer, 2004.
- Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Joseph Y-T. Leung. CRC Press, 2004.
- Handbook on Scheduling: From Theory to Applications. Jacek Blazewicz, Klaus H. Ecker,
- Erwin Pesch, Günter Schmidt, Jan Weglarz, Springer, 2007.
Pochet, Y., & Wolsey, L. A. (2006). Production planning by mixed integer programming. Springer Science & Business Media.
Faire un stage/une thèse en Recherche Opérationelle?
Métiers de la Recherche Opérationnelle, de l'Optimisation, de l'Aide à la Décision et de la Recommandation Intelligente
Les ingénieurs et les chercheurs ayant suivi les modules du master ANDROIDE correspondants à cette coloration s'intéressent aux questions d'ordre décisionnel, que l'on appelle aussi questions stratégiques.
Souvent de structures complexes et de dimensions importantes, ces questions nécessitent le recours à des modélisations et l'utilisation d'algorithmes performants. Il peut s'agir par exemple de décider l'investissement d'une entreprise sur un marché concurrentiel (Aide à la décision), la recherche d'un plan de livraison optimal pour un convoyeur (Recherche Opérationnelle), le meilleur ordonnancement des tâches d'une usine (Ordonnancement),...
Les compétences d'un ingénieur R&D de cette coloration sont recherchées par plusieurs types d'entreprises:
- les grands groupes industriels qui possèdent des départements R&D dédiés aux problèmes Rercherche Opérationnelle et Aide à la décision, mais aussi des départements de décision stratégiques liées à la direction,
- les entreprises fournissant des consultants aux entreprises pour des problèmes ponctuels ou récurrents,
- et les éditeurs logiciels et solutions web qui ont besoin d'intégrer des méthodes et algorithmes de pointe dans leurs produits.
|
