EC0707OP0701GI - 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.

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)