EC0707OP0701GI_B - RECHERCHE ET OPTIMISATION COMBINATIORE : ALGORITHMES AVANCES ET APPLICATIONS

Objectifs

Ce cours aborde les problèmes combinatoires, c'est-à-dire à la fois discrets (variables à valeurs entières) et difficiles (nombre de « combinaisons » possibles exponentiel).
Problèmes qui se retrouvent dans de nombreuses applications industrielles présentant des enjeux économiques majeurs : positionnement d'antennes, agencement d'ateliers, tournées de ramassage des déchets, choix d'investissement pour une entreprise, etc.
Le cours d'Option vient compléter le cours de Tronc Commun en abordant un spectre large d'applications à vocation industrielle et en détaillant et comparant les algorithmes disponibles pour résoudre ces problèmes.


The lecture will address combinatorial problems, which are both discrete (integer variables) and hard (exponential number of possible assignments).
Such problems might be found in a number of industrial applications with major economic stakes : antenna placement, workshop layout, garbage collection routing problems, investment choices, etc.
The Industrial Engineering Track lecture will complete the Core Curriculum one by covering a larger spectrum of industrial-oriented applications and by investigating and comparing available solving algorithms.

Présentation

- Algorithmes de propagation de contraintes et exemples d'applications
- Plans d'expérience
- Optimization exacte : technique de Branch & Bound appliquée aux problèmes de sac-à-dos et de tournées de véhicules
- Optimisation approchée par construction : heuristiques gloutonnes, recherche à divergence limitée
- Optimisation approchée par voisinage : algorithme de descente et meta-heuristiques (recuit simulé, recherche tabou, méthodes des fourmis, algorithmes génétiques)


- Constraint propagation algorithms and application examples
- Experimental design
- Global exact optimization : Branch & Bound technique and its application to knapsack and vehicle routing problems
- Constructive approximate optimization : greedy heuristics, limited discrepancy search
- Approximate optimization through neighborhood search : hill climbing algorithm and metaheuristics (simulated annealing, taboo search, ant optimization, genetic algorithms)

Pré-requis

Recommandations

Conditions d'évaluation

(0.8*CC1+1.2*DS1)/2

CC1 : Contrôle Continu 1

DS1 : Devoir Surveillé 1

Bibliographie

Pas de référence bibliographique spécifique. Les étudiants sont encouragés à approfondir les notions vues de manière autonome : en premier lieu sur internet (Wikipedia pour démarrer), complété éventuellement d'une recherche de livres de référence à la bibliothèque
Pas de référence bibliographique spécifique. Les étudiants sont encouragés à approfondir les notions vues de manière autonome : en premier lieu sur internet (Wikipedia pour démarrer), complété éventuellement d¿une recherche de livres de référence à la bibliothèque.