Algorithmes pour l’optimisation en nombres entiers

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 24 heures
  • Temps de travail personnel : 51 heures

Objectifs et compétences

Objectifs :
Modélisation de problèmes à l'aide de modèles de graphes et de flots.

Programmation dynamique, formulation sous la forme d'un problème de plus court chemin.

Problèmes multi-flot, relaxation Lagrangienne, décomposition par les prix (Dantzig) et par les ressources (Benders)

Introduction aux problèmes de tournées de véhicules : formulations, variantes, relaxation, approche de décomposition.

Problèmes de parcours des arcs d'un réseau : formulations, variantes, cas faciles.

Classes de complexité, réduction polynomiale, NP-complétude, diviser pour régner, matroïdes, programmation dynamique.

Compétences :
  • Être en capacité d'investir ses connaissances et aptitudes dans le cadre d'une mise en situation professionnelle.
  • Etre capable de communiquer des résultats à l'écrit et à l'oral
  • Assurer une veille scientifique et professionnelle
  • Connaître le ou les champs professionnel(s) associé(s) à la discipline.
  • Etre en capacité d’investir ses connaissances et aptitudes dans le cadre d’une mise en situation professionnelle
  • Etre capable de communiquer des résultats à l'écrit et à l'oral
  • Etre capable d’adapter les modèles théoriques à un objet de recherche ou aux réalités de terrain.

  • Être autonome dans le travail
  • Poursuivre par soi-même ses apprentissages ; se préparer à se former tout au long de la vie
  • Savoir se remettre en question, faire preuve d'esprit critique

  • Connaître et mettre en application les principaux modèles mathématiques intervenant dans les différentes disciplines connexes du domaine Sciences et Technologies mais aussi des autres domaines
  • Construire et rédiger une démonstration mathématique synthétique et rigoureuse.
  • Être capable de traduire un problème simple en langage mathématique.
  • Être initié aux limites de validité d’un modèle (par conduite de situations de modélisation).
  • Mettre au point un nouvel algorithme ou adapter un algorithme existant pour répondre à un problème donné

  • Être en capacité de savoir aborder un problème complexe.

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

Session 1

> Examen terminal écrit 3h00 Coef. 0,67

> CC Coef. 0,33

Session 2

>Examen écrit 3h sauf si faible effectif (<=2) -> oral

max { 1/3 CC + 2/3 note rattrapage , note rattrapage}

Lectures recommandées

l'ensemble des références bibliographiques est communiqué au début des enseignements

Responsable de l'unité d'enseignement

Francois Clautiaux

Enseignants

la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements