Aller au menu Aller au contenu
Une formation ambitieuse
Ecole de référence pour la formation d'ingénieurs en génie industriel
Une formation ambitieuse

> Formation > Cursus ingénieur

UE Méthodes avancées en Programmation linéaire et Applications - 5GUC3419

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Volumes horaires

    • CM : 27.0
    • TD : 27.0
    • TP : -
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 6.0
  • Responsables : Olivier BRIANT

Objectifs

Être capable de modéliser correctement un problème comme un programme linéaire en variables entières ou mixtes. Comprendre les diverses techniques de résolution, et savoir les utiliser sur des problèmes concrets.

Contenu

La programmation linéaire en variables continues, entières ou mixtes est un outils très performant pour résoudre de nombreux problèmes d'optimisation. La littérature scientifique est abondante sur le sujet et sur ses applications, et les progrès récents sont très significatifs. Pour que la résolution d'un modèle soit efficace, il faut identifier dans un premier temps le type de problème qu'on souhaite résoudre et identifier le bon modèle. Il faut ensuite renforcer ce modèle pour accélérer sa résolution. Cela passe par la compréhension des algorithmes de résolution utilisés, et l'identification de la structure même des problèmes.

Cette UE sera décomposée en 3 parties :

  • un cours magistral abordant les points théoriques
  • la lecture d'articles scientifiques, la rédaction d'une fiche de lecture, et une présentation orale
  • un projet informatique d'application de la théorie sur un problème concret

Les points théoriques abordés durant le cours seront :

  • Problèmes de flot :
    • Algorithme de « Network simplexe »
    • Flots généralisés
    • Flots de coût minimum à coût convexe
  • Qualité des formulations
    • Principe de l'algorithme de Branch & Bound
    • Prétraitements
    • Notions de coupes : exemples des coupes de Gomory entières, et mixtes
    • Algorithme de Branch & Cut
  • Méthodes de décomposition et applications
    • Relaxations lagrangiennes
    • Décompositions de Dantzig-Wolfe
    • Algorithmes de résolution du dual lagrangien : sous-gradient, Kelley
    • Notions de stabilisation des variables duales
    • Autres méthodes de décomposition
    • Algorithme de Branch & Price

Prérequis

Cours de programmation linéaire et de théorie des graphes niveau M1

Contrôles des connaissances

Session 1 :
? Examen écrit : 40 %
? Lecture d'un article, rédaction d'une fiche de lecture, présentation orale : 20 %
? Projet : 40 %

Session 2 : Examen écrit ou oral

Session 1:
E1 : Examen Ecrit
CC : Lecture d'article
P : Projet
N1 = 40% E1 + 20% A + 40% P

Session 2:
E2 : examen écrit ou oral
N2 = 100% E2

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Master 2 GI GO - Semestre 9
  • Cursus ingénieur - Ingénieur ICL - Semestre 9
cf. l'emploi du temps 2019/2020

Informations complémentaires

Code de l'enseignement : 5GUC3419
Langue(s) d'enseignement : FR

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

Bibliographie

  • Network flows: theory, algorithms, and applications, J. B. Orlin, R. K. Ahuja et T. L. Magnanti, 1993, Prentice-Hall, Inc.
  • Integer Programming, L. A. Wolsey, 1998, Wiley
  • Modern Heuristic Techniques for Combinatorial Problems, C. R. Reeves, 1993, John Wiley \& Sons, Inc.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 20 juin 2019

Programmes pédagogiques

2019-2020 Cursus ingénieur
1ère année présentation
Semestre 5 - Semestre 6
Filière ICL présentation
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10
Filière IdP présentation
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10

2019-2020 Cursus ingénieur par apprentissage
Filière IPID présentation
Semestre 5 - Semestre 6
Semestre 7 - Semestre 8
Semestre 9 - Semestre 10

Contacts

Responsables pédagogiques
Directeur des études Yannick Frein
Responsable année 1 Pierre David
Responsable filière ICL
Hadrien Cambazard
Responsable filière IdP Guillaume Thomann
Responsables apprentissage filière IPID
Nicolas Catusse
Olivier Boissin


Service scolarité
Responsable Laure Jouffray
Gestionnaire 1ère année
Valérie Demicheli
Gestionnaire 2ème année
Myriam Reinbold
Gestionnaire 3ème année
Hélène Lemaire
Relations entreprises / apprentissage
Christine Ancey
Gestionnaire apprentissage 2ème année
Sylvie Malandrino

Echanges internationaux
Nadia Dehemchi
Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes