Vous êtes ici

  1. Accueil
  2. Combinatorial optimisation and related algorithms (COBRA)

Combinatorial optimisation and related algorithms (COBRA)

Combinatorial optimisation and related algorithms (COBRA)

En pratique :

Langue principale : français
Nombre de crédits européens : 5

Description du contenu de l'enseignement

: 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 à acquérir

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.