Présentation

Ce cours d'une 30aine d'heures 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.

Des TPs et un projet y sont proposés 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é.

Plan du cours

• Cours 1
  • 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
  • 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
  • Méthode de coupes et branchement (Branch-and-Cut)
  • TP: Algorithme Branch-and-Cut avec CPLEX
  
  
• Cours 4
  • Modélisation et Algorithmes de coupes
  • TME: Algorithme Branch-and-Cut avec CPLEX (suite)
  • PROJET: présentation du sujet
  
  
• Cours 5
  • Approches polyédrales
  • PROJET: séance de suivi du projet
  
  
• Cours 6
  • Approches polyédrales (suite)
  • PROJET-TME: suivi de projet
  
  
• Cours 7
  • Relaxation et décomposition Lagrangienne
  • Décomposition et génération de colonnes (Branch-and-Price)
  • PROJET: séance de suivi du projet
  
  
• Cours 8 (08/01/20)
  • Caractérisation de polyèdres et exercices
  • PROJET: séance de suivi du projet
  
  

Documents de cours et TD

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		Relaxation et décomposition Lagrangienne
Partie	F	Génération de colonnes (Branch-and-Price)

TD: Cahier d'exercice

TME

Projets

• Projet "Autour des problèmes de tournées:
  
Projet_Production_Routing1819.pdf
Instances CVRPLIB


• Projet "Autour du problème de Production et Distribution Intégré"
  
Projet_Production_Routing1718.pdf
Les instances du projet
Les instances
Un document décrivant les instances
Du code C++ utile pour la manipulation d'instances


• Projets courts
  Cadre général des projets Projet_Maoa.pdf
  Projet RCPS: Projet_RCPSP.pdf
  Projet_conception_circuit_analogique.pdf
  Projet Verre de Spin Projet_Spin_Glasses.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.