Introduction à la programmation en variables entières

Informations

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

Programme

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

Objectifs et compétences

Objectifs :
Donner les outils standard de modélisation et de résolution algorithmique de l'optimisation discrète : méthodes exactes et approchées.

Optimisation dans un espace discret : approche énumerative et explosion combinatoire.

Complexité des algorithmes (empirique, en moyenne et du pire des cas).

Problèmes faciles/difficiles : introduction à la théorie de la complexité (classes P, NP, NPC, NP-hard et reduction de problèmes);

Formulation par la programmation entière : modélisation avec des variables entières, qualité de formulation.

Optimisation exacte versus approchée : borne primale et duale, relaxation combinatoire, relaxation linéaire, relaxation lagrangienne, surrogate, heuristiques constructives.

Méthode de séparation et évaluation (branch-and-bound).

Notion d'inégalité valide, problème de séparation.

Compétences :
  • Etre capable de communiquer des résultats à l'écrit et à l'oral
  • Connaître le ou les champs professionnel(s) associé(s) à la discipline.
  • Se mettre en recul d’une situation, s’auto évaluer et se remettre en question pour apprendre
  • Développer un esprit critique envers les données existantes
  • Etre en capacité d’investir ses connaissances et aptitudes dans le cadre d’une mise en situation professionnelle
  • 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
  • Maitriser les concepts fondamentaux en mathématiques et en probabilité
  • Maitriser les bases scientifiques de la modélisation et les outils modernes du langage scientifique : mathématiques, statistiques, méthodes numériques

  • 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

  • Ê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 : Contrôle continu - coef. 1/3 + Examen final (3 heures) - coef. 2/3

Session 2 : Note contrôle continu session 1 - coef. 1/3 + Examen final (3 heures) - coef. 2/3. L'examen final pourra se faire à l'oral en cas d'effectif faible.

Note éliminatoire : 5

La règle du max s'applique pour la deuxième session.

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