Ensimag Rubrique Formation 2022

Recherche opérationnelle avancée - algorithmes pour l'IA - 4MMROA6

  • Volumes horaires

    • CM 16.5
    • Projet -
    • TD 16.5
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

Modéliser et résoudre des problèmes de décisions complexes par des méthodes avancées.

Responsable(s)

Moritz MUHLENTHALER

Contenu(s)

Fondements méthodologiques:
• Programmation Linéaire en Nombres Entiers :

  • complexité ;
  • méthodes des coupes ;
    - couplages ;
    - cycle hamiltonien et voyageur de commerce.
    • Programmation Dynamique :
  • exemples de modélisation, équation de Bellman
  • application au sac à dos (simple et multiple) ;
    • Algorithmes approximatifs et heuristiques.
  • méthodes gloutonnes ;
    -algorithmes avec l’approximation garantie ;
    4) Processus de décision markovien (Markov decision process) :
    - le plus court chemin stochastique.

Applications (un sous-ensemble des suivantes - liste non exhaustive):

• Problèmes de Localisation (k-centre, p-médian, Facility location)
• Gestion des stocks déterministe et stochastique
• Ordonnancement / Job-scheduling
• Problèmes de tournées de Véhicules
• Pilotage de robots
• Optimisation en finance : pricing, index funds
• Yield management
• Network design
• Conception de circuits
• etc...

Prérequis

Cours de Recherche Opérationnelle de la 1ère année (les notions des graphes et de la programmation linéaire).
Il est vivement conseillé de suivre en amont le cours d’Optimisation Combinatoire mais la connaissance de certains modèles traités dans ce cours sera suffisante.

Contrôle des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :

SESSION NORMALE :
Type d'examen : examen écrit
Durée : 3h
Documents autorisés : une feuille A4 recto-verso manuscrit
Documents interdits : livres, supports du cours.
Matériel interdit : Calculatrices.

SESSION DE RATTRAPAGE :idem session normale.

N1=E1
N2=E2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Filière MMIS - Semestre 8
cf. l'emploi du temps 2023/2024

Informations complémentaires

Code de l'enseignement : 4MMROA6
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

Integer Programming, L. Wolsey
Theory of Linear and Integer Programming, A. Schrijver
Dynamic programming and optimal control (vol. I et II), D. Bertsekas
Optimisation Methods in Finance, G. Cornuejols and R. Tütüncü
Combinatorial Optimization: Algorithms and Complexity Christos H. Papadimitriou,Kenneth Steiglitz Dover Publications,Inc
Iterative Methods in Combinatorial Optimization Lap Chi Lau Cambridge

Recherche opérationnelle et réseaux Gerd Finke, Lavoisier.