Partager cette page :
Discipline(s) : Infomatique et télécommunications

Optimisation combinatoire

Semestre Semestre 2
Type Facultatif
Nature UE

Pré-requis

Algorithmique de niveau L3, notions de NP-complétude.

Objectifs

Ce cours a pour objet l'étude théorique de diverses problèmes d'optimisation en vue la conception et la mise en oeuvre des algorithmes de résolution. La première partie est centrée sur la programmation mathématique, considérée comme le cœur de l'optimisation combinatoire et de la recherche opérationnelle. Les méthodes présentées ici sont basées sur la théorie de la programmation linéaire et de la dualité, ainsi que sur les techniques de résolution de Programmes Linéaires Mixtes en Nombres Entiers (PLMNE). Ces méthodes, très développées aujourd’hui, permettent de concevoir des algorithmes efficaces (polynomiaux) pour la résolution des grands classiques du domaine tels que le problème de localisation et de transport, d'optimisation de flux dans les réseaux, etc. Une analyse approfondie de la complexité de chacun des algorithmes est donnée. Un accent particulier est réservé aux techniques de modélisation avec une prise en compte de conditions logiques.

La seconde partie apporte un complément à l'algorithmique vue en Licence en insistant sur les techniques de backtracking et de branch-and-bound comme première solution pour résoudre des problèmes NP-complets. Nous considérons les problèmes d'optimisation dits "NP-complets" tels que la répartition de charges de processeurs, la selection de centres, le problème du sac à dos, la couverture de sommets de poids minimal. Pour les problèmes d'optimisation, nous explorons, à titre culturel, la famille des algorithmes de recherche locale (local search), dont le "recuit simulé". Nous aborderons ensuite une initiation à la théorie des jeux pour modéliser des problèmes réalistes dont les solutions recherchées se ramènent à calculer des équilibres (de Nash, forts), etc.; typiquement, nous considérons des problèmes de routages dans un réseau et des problèmes d'allocation de ressources.

Compétences acquises : A l’issue de ce cours l’étudiant sera apte à reconnaître les problèmes d’optimisation principaux et d’utiliser les techniques adéquates pour leur résolution.

Contenu

Cours 1ère partie
  • Techniques générales de modélisation, prise en compte de conditions logiques
  • Programmation linéaire (PL) et dualité
  • Théorème des valeurs entières (matrice totalement unimodulaire)
  • Applications :
    • Dans les réseaux (le problème du transport et d’affectation, le problème du coût minimum et flot compatibles) ;
    • Dans la bioinformatique (assemblage du génome).
    • Dans l’analyse des réseaux sociaux.
Cours 2ère partie
  • Brefs rappels sur la NP-complétude
  • Recherche exhaustive : Backtracking et Branch-and-Bound, algorithme A*
  • Pricing Method and Linear Programming Rounding
  • Local search
  • Algorithmic game theory
Travaux dirigés
  • Les travaux dirigés consistent à mettre en application les notions de cours.

Travaux pratiques
  • Les travaux pratiques permettront de modéliser certains des problèmes étudiés avec le langage AMPL et de les résoudre avec des solveurs contemporains comme CPLEX et GUROBI.

Mise à jour le 13 avril 2018