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. Seront également abordés quelques méthodes pour l'optimisation non-linéaire en nombres entiers.

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.

La revue grand public Tangente propose un Hors-Série spécial Recherche Opérationelle auquel plusieurs intervenants de ce module ont participé.

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 (07/10/20) [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

  • Cours 2 (14/10/20) [Pierre Fouilhoux]
    • Rappels sur Branchement et Évaluation (Branch-and-Bound)
    • Formulations non compactes: inégalités valides et renforcement
    • Méthode de coupes et branchement (Branch-and-Cut)

  • Cours 3 (21/10/20) [Thibaut Lust]
    • TME: Algorithme Branch-and-Cut avec CPLEX
    • PROJET: Présentation du sujet

  • Cours 4 (28/10/20)
    • 8h30: [Hacène Ouzia]
    •      Décomposition
    • 10h45: [Thibaut Lust]
    •      TME: Algorithme Branch-and-Cut avec CPLEX (suite)
    •      PROJET: mise en place des binômes

  • Cours 5 (04/11/20) [Hacène Ouzia]
    • Génération de colonnes
    • Relaxation Lagrangienne

  • Cours 6 (18/11/20)
    • 8h30: [Hacène Ouzia]
    •      Méthode pour l'optimisation non-linéaire en nombres entiers
    • 10h45: [Thibaut Lust]
    •      PROJET: séance de suivi du projet

  • Cours 7 (25/11/20) [Anne-Elisabeth Falq]
    • Points extrêmes et cas polynomiaux
    • Approches polyédrales

  • (02/12/20) Examen réparti 1

  • Cours 8 (09/12/20) [Anne-Elisabeth Falq]
    • Approches polyédrales (suite)

  • Cours 9 (06/12/20) [Fanny Pascual]
    • Théorie de l'ordonnancement: introduction et typologie
    • Problèmes à une machine (minimisation de la date de fin moyenne pondérée)

  • Vacances de fin d'année

  • Cours 10 (16/01/21) [Fanny Pascual]
    • Problèmes à une machine (avec dates d'échéances)
    • Problèmes à plusieurs machines

  • Cours 11 (13/01/21) [Anne-Elisabeth Falq]
    • Caractérisation de polyèdres et exercices

  • Cours 12 (20/01/21) [Safia Kedad-Sidhoum]
    • Lot-sizing: classification et formulations
    • Problèmes polynomiaux

  • Cours 13 (27/01/21) [Safia Kedad-Sidhoum]
    • Inégalités valides pour le lot-sizing

  • Cours 14 (03/02/21)
    • Soutenance projet
    • Exercices et Révisions

  • (17/02/21) Examen réparti 1

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 "Modélisation et PLNE"
(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)

TD: Cahier d'exercice partie "Modélisation et PLNE"

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.