UPMC - Master M2 ANDROIDE - Module MAOA

MAOA

Méthodes Avancées et applications industrielles

en Optimisation Combinatoire et en OrdonnAncement



Plan de la page

Module MAOA

Organisation du module

TME

Projets

Documents

Annales d'examens

Ouvrages de références


Carrière en RO

Faire un stage/une thèse en Recherche Opérationelle?

La Roadef
Forum des stages en RO
Forum des emplois en RO

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)
    • Problèmes récents en RO

  • 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)

Intro Introduction
Rappel Résolution exacte ou à garantie expérimentale
Partie A Formulations compactes et modélisations
Rappel Branchement et évaluation (Branch-and-Bound)
Partie B Cas polynomiaux
Partie C Méthodes de coupes (Branch-and-Cut)
Partie D Approches polyédrales.pdf
Partie E Caractérisation de polyèdres
H-Prog (Hors Programme) Relaxation et décomposition Lagrangienne
Partie F Génération de colonnes (Branch-and-Price)

Pour impression: Le document de cours complet

TD: Cahier d'exercice

Partie "Lot-Sizing"
(Safia Kedad-Sidhoum)

Cours Lot-Sizing

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.