EMN - Ecole des Mines de Nantes

Contexte

Prendre une décision, opérationnelle ou stratégique (par exemple, planifier une tournée de livraison), c'est déterminer les options (l'ordre et les dates de visite des clients) qui répondent à plusieurs impératifs simultanés (la durée des trajets, la capacité du camion de livraison, la disponibilité des clients, les horaires de travail du chauffeur, etc.), puis choisir parmi ces options la meilleure selon un ou plusieurs critères donnés (minimiser les coûts de transport ou livrer les bons clients au plus tôt). Généralement l'ensemble des options possibles est dénombrable mais potentiellement infini, de sorte qu'il est impossible de l'énumérer entièrement en temps raisonnable, aussi performant que soit le système de calcul utilisé.
L'optimisation combinatoire est la discipline de l'étude théorique et pratique de ces problèmes de décision.
Elle recouvre l'ensemble des outils analytiques, logiques et algorithmiques qui permettent la résolution de ces problèmes difficiles. Émanant des mathématiques par la recherche opérationnelle et de l'informatique par la théorie de la complexité et lintelligence artificielle, ces outils se partagent en grandes classes technologiques -- telles que les algorithmes de graphe, la programmation linéaire en nombres entiers, les metaheuristiques, la programmation par contraintes -- définissant ainsi différents modes et objectifs de résolution.
De manière transversale, les outils se combinent en grands domaines d'application telles que l'ordonnancement, le transport, l'analyse de données, la bio-informatique, la finance, etc.

Objectifs

Objectifs généraux

Cette unité de valeurs aborde un large éventail de techniques avancées de l'optimisation combinatoire au travers de l'étude pratique de problèmes types issus de situations réelles.
Les techniques abordées sont principalement:
- procédures par séparation et évaluation, recherches locales et programmation dynamique;
- dualité, relaxations et décompositions en programmation linéaire en nombres entiers;
- algorithmes de chemins, de flots et de recouvrement dans les graphes;
- heuristiques, metaheuristiques et algorithmes d'approximation;
- reformulation, contraintes globales et propagation en programmation par contraintes.
Les classes de problèmes étudiés sont, par exemple: planification de tournées, ordonnancement, affectation, placement géométrique, planification d'horaires.

Objectifs operationnels

Les objectifs de formation sont pour l'étudiant:
- asseoir, augmenter et approfondir sa connaissance des techniques et des problèmes classiques de l'optimisation combinatoire;
- se confronter à la mise en oeuvre pratique des techniques, depuis la compréhension d'un problème jusqu'au calcul et à l'analyse de solutions, en passant par: l'analyse des besoins, l'étude de complexité, la modélisation mathématique, le choix des techniques, la conception et l'implémentation d'algorithmes, l'utilisation de librairies et de solveurs, la conception d'un dispositif expérimental.

Competences requises

Compétences requises

Cette unité de valeurs recquiert des connaissances solides en algorithmique, programmation, programmation par objets et structures de données; et des connaissances de base en programmation linéaire (modélisation, simplexe, dualité), en recherche opérationnelle (modèles et algorithmes de graphes, heuristiques, recherche arborescente) et en programmation par contraintes (consistances, propagation et recherche).

Unites de valeurs cibles

Codes UVs cibles

– UV GS1 Recherche Opérationnelle
– UV GS1 Langages et Techniques pour l’Aide à la Décision

UVs cibles

– UV GS2 Projet d'option

Contenu et organisation pedagogique

Contenu de l'UV

Cette unité de valeurs se déroule sur l'intégralité du semestre de GS2.
Elle se compose de 3 modules d'apprentissage par la pratique et par problèmes (APP) d'un module dédié aux problèmes et méthodes d'ordonnancement et d'un module d'approfondissement à la pratique de la programmation par contraintes.

* Pratique et Problèmes
Ce module comporte 3 sessions d'apprentissage par la pratique et par problèmes. Chaque session est le cadre d'un apprentissage collectif (par groupes de 3 à 4 élèves) actif, à travers l'étude de divers problèmes d'optimisation combinatoire dans une thématique donnée:
- APP1: Graphes et Transports;
- APP2: Affectation et Placement;
- APP3: Ordonnancement et Planification d'horaires.
Les groupes de travail doivent répondre à chaque problème posé par une analyse du problème et une méthode de résolution.
Un carnet d'accompagnement est fourni aux groupes pour guider leur étude. Il se présente comme une série de questions, d'exercices, de points théoriques, d'informations historiques, ou de références bibliographiques.
Sur la durée d'une session, chaque groupe doit réaliser autour d'une problématique précise (au choix): un rapport d'étude, l'implémentation d'une méthode de résolution (basée éventuellement sur un solveur libre) et une analyse théorique et expérimentale de la solution.
Ce module donne lieu à l'acquisition et à l'étude de techniques classiques d'optimisation combinatoire telles que: relaxation linéaire, surrogate, lagrangienne; décomposition de Dantzig-Wolfe et génération de colonnes; génération de coupes; heuristiques gloutonnes, recherche locale, complexité, approximation; programmation dynamique; algorithmes de Dijsktra, Floyd-Warshal, Ford-Fulkerson, Kruskal, hongrois; contraintes globales, préférences et sur-contraints, symmétries.
Parmi les problématiques étudiées, on peut citer: couplage max, flot min, couverture min, affectation, TSP, VRPTW; knapsack, multi-knapsack, bin-packing, cutting-stock, set-partitioning; ordonnancement à 1 machine, job-shop, flow-shop, RCPSP, planification d'horaires.
Intervenants: Sophie Demassey (APP1-2) et Thierry Petit (APP3), enseignants-chercheurs (Contraintes, EMN)

* Programmation Par Contraintes
Ce module de formation approfondit les aspects pratiques des technologies des contraintes. Dispensé sous formes de travaux pratiques, l'apprentissage porte sur l'usage d'un solveur de contraintes, Choco/Java en l'occurence, pour la modélisation et la résolution de problèmes combinatoires. Les exercices proposés portent notamment sur: reformulation et contraintes redondantes, heuristiques de sélection et stratégie de recherche, implémentation de contraintes globales. Deux cours magistraux présenteront les concepts centraux de la modélisation et de la résolution en contraintes.
Intervenants: N. Beldiceanu, Ch. Prud'homme, S. Demassey, , enseignants-chercheurs (Contraintes, EMN)

Activités pédagogiques

- APP 1 (18h - septembre-octobre): projet 15h, évaluation individuelle écrite 3h
- APP 2 (18h - novembre): projet 15h, évaluation individuelle écrite 3h
- APP 3 (18h - décembre-janvier): projet 15h, évaluation collective orale 3h
- programmation par contraintes (27h - septembre-octobre/décembre): cours 6h, TD/TP 18h, TP noté 3h

Supports pédagogiques

- APP: carnets d'étude et sélection d'articles scientifiques (sur Campus); une sélection d'ouvrages est mise à disposition des étudiants en séances. NB: la recherche bibliographique fait partie intégrante de l'activité attendue des APP.
- PPC: feuilles d'exercices (sur Campus); documentation et exemples choco: http://choco.emn.fr. Support de cours et catalogue de contraintes globales: http://www.emn.fr/x-info/sdemasse/gccat/

Critere et mode d'evaluation

Critères d"évaluation

- APP: évaluations individuelles écrites (sessions 1 et 2), évaluation collective orale (session 3), rapport+implémentation/groupe/session;
- PPC: TP noté.
Les devoirs individuels ont pour objectif d'évaluer l'acquisition des connaissances théoriques et la capacité à mobiliser ces connaissances dans un contexte nouveau.
Les implémentations (y compris le TP noté) ont pour objectif d'évaluer la capacité à mettre en pratique ces connaissances ainsi que de conduire une expérimentation et de réaliser une analyse de performance.
Les rapports écrits et la soutenance permettent d'évaluer la capacité à communiquer sur un sujet scientifique.
Dans ces différents exercices, la rigueur scientifique et technique est un critère d'évaluation important ainsi que, dans une moindre mesure, la curiosité et l'imaginativité.

Nombre d'évaluations

7