Module A8 : OCRO Optimisation Combinatoire et Recherche Opérationnelle

Accueil

Objectif de ce module

Pour le programme officiel du cours de module C09 voir le :

• Cours C9-1 - Programmation mathématique
• Cours C9-2 - De la programmation mathématiques à la programmation par contraintes: modèles pour l'optimisation discrète
• Cours C9-3 - Complexité et graphes
• Cours C9-4 - Résolution des problèmes difficiles d'optimisation combinatoire : méthodes exactes et approchées

Cette page Web ( http://www.ensta.fr/~diam/ocro ) est essentiellement dédiée au deux cours C9-1 et C9-4 qui font l'objet d'un projet consistant en un problème à modéliser et à résoudre d'une part par une approche exacte C9-1), et d'autre part à l'aide d'une méta-heuristique (C9-4).

Ce module de quatre cours fournit les outils théoriques et pratiques de résolution des grandes classes de problèmes combinatoires qui apparaissent en Recherche Opérationnelle : problèmes de voyageur de commerce, de tournées, de localisation (par exemple, localisation d'entrepots), d'ordonnancement, d'affectation généraliséee (fabrication d'emplois du temps), de routage dans les réseaux, d'allocation de fréquence, etc. On apprend à distinguer les problèmes faciles (polynômiaux) des problêmes difficiles (NP-durs), grâce à la théorie de la complexité, et à traiter les problèmes polynômiaux à l'aide d'algorithmes de graphes (chemins, flots, etc). On donne ensuite, en l'illustrant par des applications, une idée de l'état de l'art. On présente ainsi les grandes classes de méthodes exactes ou d'heuristiques raisonnées de résolution des problèmes difficiles, à base soit de programmation mathématique (branch and bound, programmes linéaires en nombres entiers, etc.), de méthodes de voisinages (tabou, recuit, etc.), ou de programmation par contraintes.

Mots Clés : complexité, graphes, recherche opérationnelle, Optimisation Combinatoire, Heuristiques.

Les contacts

Responsable du module C9 (OCRO)

Soutien technique

    http://www.ensta.fr/~diam/

Professeur C9-1

 (EDF)

Professeur C9-2

  http://www.ensta.fr/~mcosta

Professeur C9-3

  http://www.ensta.fr/~mcosta

Professeur C9-4

  (CELAR/TCOM - BP7419 35174 Bruz Cedex)

Autres conférenciers (pour un ou plusieurs cours)

- Guillaume Rochard  (e-Lab de Bouygues) :    Programmation par Contraintes (CP ou PPC)

- Matthieu Chardy  (Orange) :    Présentation de problèmes de recherche opérationnelle dans l'industrie (Orange Telecom)

Les cours

Seuls les instructions particulières sont indiquées ici. Les transparents, quand ils sont disponibles, sont accessibles depuis le menu de gauche de cette page.

Travaux Pratiques

C9-1 : Travaux pratiques de PLNE et coupes (M. Diamantini)

Objectifs :

• présenter le programme mathématique d'un problème classique, le TSP ;
• faire manipuler des solveurs, en l'occurrence Cplex avec le langage OPL ;
• faire sentir la différence entre un programme en nombres entiers et sa relaxation continue ;
• donner l'occasion de faire un peu de modélisation, et montrer qu'un problème peut se modéliser de plusieurs façons différentes.

C9-1 : Travaux pratiques de PLNE et Génération de Colonnes (O. Klopenstein)

Objectifs : Implantation en OPL de l'exemple de multifots vu en cours

Les détails sont fournis lors de la séance de TD

Le projet C9-1 / C9-4

Le sujet du projet de recherche opérationnelle est commun aux deux cours C9-1 et C9-4. Seul le travail demandé diffère. Pour des raisons pratiques, deux versions différentes du sujet, adaptées à chaque cours seront distribuées séparément, et deux rapports différents seront à rendre.

Sujet du projet

GoTIC : Gestion Optimale des tournées pour les Techniciens d'Intervention Clients

Utilitaires

Deux scripts Ruby vous sont proposés pour simplifier la mise au point de vos programmes. Ces commandes sont accessibles de la même façon que les commandes de cplex (oplrun, ...) par usediam ro.

• gotic est un validateur avec de nombreuses options vous permettant entre autre :
  • d'obtenir des statistiques sur l'instance à traiter,
  • de générer une version OPL de l'instance,
  • de valider votre solutions (vérification des timing, ...),
  • de générer le format détaillé de la solution.
  Taper gotic -h pour tout savoir sur cette commande
• goticvisu permet de visualiser une solution réalisable (et éventuellement d'enregistrer une version eps)
  Syntaxe : goticvisu mini.dat mini.sol

Modalités des cours/projets/examens

Modalité pour le cours C9-1 (méthodes mathématiques)

La note du cours C9-1 sera composée de 10 points pour le projet et de 10 points pour l'examen. La validation du cours requerra 3 points minimum à chacune de ces deux épreuves.
Les dates à retenir sont les suivantes :

• Lun 19 sept 2011 (lors de la séance du TP plne)
  - Distribution du sujet de projet pour le cours c9-1 ;
• Lun 26 sept 2011
  - rendu du modèle PLNE correspondant à la question 1 du sujet. Ce pré-rapport comptera pour deux points sur les dix de la partie projet,
  - une version corrigée vous sera alors proposée que vous devrez implanter à l'aide du langage OPL de Cplex ;
• Lun 03 oct 2011 (matin)
  - rendu (avant la séance de TD en salle info) du code OPL correspondant à l'approche frontale que vous aurez finalement adopté (par email cf. lien ci-dessous) ;
• jeu 13 oct 2011 :
  - remise par courrier électronique d'une archive du rapport pré-final (incluant les programmes en OPL pour l'approche frontale, pour la décompostion lagrangienne ainsi qu'un guide pour l'exécution de vos programmes).
  - Cette archive sera envoyée par courrier électronique à : encadrement OCRO C9-1
• Lun 17 oct 2011
  - examen sur table (durée : 1h30),
  - remise du rapport écrit final avec le code,
  - et soutenance orale des projets (10mn (c'est court !) par groupe).

Modalité pour le cours C9-4 (méta-heuristiques)

Les dates à retenir sont les suivantes :

• Lun 23 janvier 2012
  Remise par courrier électronique d'une archive contenant les sources d'un programme permettant de lire un fichier d'instance dont le nom est passé en paramètre, et qui génère une solution au format requis.
  Cette archive sera envoyée par courrier électronique à : encadrement OCRO C9-4
• Pour le 8 février 2012
  Chaque groupe devra remettre par courriel le rapport final et le programme permettant de résoudre les instances proposées ;
• Lun 13 février 2012 (jour de soutenance)
  
  • Contrôle écrit (moins d'une heure, à préciser).
  • Une annexe comportant des corrections éventuelles ou des résultats complémentaires pourra être remise.
  • Soutenance par groupe avec vidéo-prejecteur et démo.

./

retour ENSTA / ~diam / ocro /      modif : 16/01/2012      URL originale : http://www.ensta.fr/~diam/ocro Auteur : Maurice Diamantini      URL originale : http://www.ensta.fr/~diam/ocro    modif : 16/01/2012