Vous êtes ici : FIL > Portail > Master Informatique > M2 MOCAD > OC

Optimisation Combinatoire

Nombreuses applications peuvent être vues comme des problèmes d'optimisation. L'optimisation concerne par exemple la minimisation du risque, du temps, du cout ou la maximisation de la qualité, du gain, ou de l'efficacité. La conception d'algorithmes et de méthodes efficaces pour l'optimisation est au coeur de plusieurs logiciels pour la science et l'industrie. Par exemple, il existe plusieurs façons pour :
  • Concevoir un réseau afin d'optimiser le coût et la qualité de service
  • Identifier, classifier et extraire des pages webs traitant d'un même sujet
  • Planifier des tâches pour optimiser le temps d'attente et la disponibilité
  • Déterminer l'itinéraire à emprunter pour arriver à destination au plus tôt en évitant les axes engorgés
  • Réguler un réseau électrique ou planifier le traffic aérien pour minimiser l'impact environnemental
  • Trouver comment deux molécules peuvent s'associer
Tous ces exemples ne sont qu'un échantillon extrêment petit du panorama que couvre l'optimisation et ses applications.

Cette UE a pour objet l'apprentissage de techniques de modélisation et d'outils algorithmiques pour la résolution de problèmes d'optimisation combinatoire. Un problème d'optimisation combinatoire consiste à trouver la meilleure solution dans un ensemble discret de solutions possibles, c'est à dire la solution qui optimise le (ou les) objectifs recherchés. En général, l'ensemble de solutions possibles est fini mais de taille très grande. Même avec toute la puissance de calculs dont dispose les ordinateurs d'aujourd'hui, trouver la meilleure solution en utilisant une stratégie naive, par exemple en testant toutes les solutions possibles, peut s'avérer extrêment couteux voir impossible dans un temps raisonnable pour les applications visées. Dans cette UE, nous présentrons les notions essentielles permettant de concevoir et d'implanter des méthodes efficaces pour la résolution d'un problème d'optimisation combinatoire.

Nous examinerons deux grandes classes de méthodes :
  • Les méthodes exactes : celles qui permettent de déterminer la solution optimale, c'est à dire la meilleur solution parmis toutes celles possibles
  • Les méthodes approchés : celles qui permettent de déterminer une solution qui se rapproche très près de la solution optimale. Bien que non optimales, ces méthodes s'avèrent en effet très efficaces et bien addaptées sur des problèmes pratiques de très grande taille.

L'accent sera mis en particuier sur la deuxième classe de méthodes en présentant les concepts et techniques sous-jacentes et leurs applications à différents problèmes.

Au terme de cette UE, les étudiants sauront modéliser et analyser ces problèmes et développer et/ou intègrer des solutions logicielles s'appuyant sur des méthodes algorithmiques avancées en optimisation combinatoire.

Responsable

Bilel Derbel

Volume horaire

Crédits

5 ECTS

dernire modification : 22/09/2016 15:29:18

Objectifs

Le module a pour objet l'apprentissage de techniques, modèles et certains outils de résolution de problèmes d'optimisation combinatoire. L'objectif du cours n'est pas de devenir spécialiste des méthodes de résolution, mais d'avoir une idée sur les modèles et techniques à utiliser en fonction des problèmes et des ressources rencontrées dans des situtations réélles. En complémentarité avec les autres modules de la spécialité, l'étudiant aura acquis les bases pour la modélisation et la résolution de problèmes complexes en optimisation combinatoire et en aide à la décision. L'étudiant saura identifier et analyser ces problèmes afin d'utiliser les outils algorithmiques nécessaires à leur résolution. Il sera capable de développer et/ou d'intégrer des solutions logicielles s'appuyant sur des méthodes algorithmiques avancées en optimisation combinatoire.
(voir l'onglet presentation pour plus d'informations) 

Contenu

Dans une première partie, le cours met l'accent sur la modélisation des problèmes d'optimisation combinatoire (sous forme de graphe, linéaire, etc). Dans une deuxième partie, on abordeara les méthodes de résoultions exacte et approchées. En particulier, l'acent sera mis sur les méta-heuristiques qui sont des méthodes génériques de résolution approchées particulièrement performantes pour des problèmes de grande taille. Enfin, en dernière partie on abordera les problèmes multicritères et les notions de bases qui peremettent de les traiter. Ces problèmes ont la particularité d'avoir plusieurs fonctions de coûts contradictoires à optimiser simultanement. Par exemple, déployer le minimum d'antennes radios (minimiser le cout globale des antennes) pour couvrir un maximum des zones (maximiser la couverture).

  • Cours :
    • Introduction : modélisation de problèmes d'optimisation (rappels, graphes, programmation linéaires, etc)
    • Méthodes exactes (Branch\&X, etc) 
    • Méthodes approchées et méta-heuristiques (recherches locales, algorithmes évolutionnaire, etc)
    • Introduction à l'optimisation multi-objectives (front pareto) 
  • TD/TP : modélisation de problèmes type et mise en pratiques des méthodes vue en cours. Le exercices s'appuieront sur des études de cas concrets issus de problématiques réelles (logistique, des télécom, et de l'extraction d'information). Implémentation : langage de programmation c/c++, bibliothèques d'optimisation combinatoire.

Bibliographie


dernire modification : 22/09/2016 15:28:21
Séance Cours TD/TP Remarque
1 08/09 Introduction à l'optimisation combinatoire
Heuristiques constructives (SMTWTP) Bilel Derbel
2 15/09 Recherche Locale -- Hill-Climbing First/Best improvements (SMTWTP Partie 1) Bilel Derbel
3 22/09 échapper aux optimas locaux
  • VND
  • Recheche stochastique simple
    • randomized iterative improvement
    • Metroplis
    • recuit Simulé
VND (SMTWTP Partie 2) Bilel Derbel
4 29/9 Recherches itératives avancées (ILS, VNS, TS) SMTWTP : recherches itératives avancées Bilel Derbel
5 6/10 Étude de cas (Sales Summit Scheduling) -- hyper-heursitiques suite Bilel Derbel
6 12/10 Suite Suite Bilel Derbel
7 19/10 Algo. génétiques SMTWTP GA, MA Bilel Derbel
8 2/11 Ants; (Autre lecture: ACO SMTWTP) Suite Bilel Derbel
9-10-11 -- Optimisation Multiobjectif Optimisation Multiobjectif Arnaud Liefooghe

dernire modification : 25/09/2017 11:17:04