Détails du cours OROC-RO-PM

Mathematical Programming

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : OROC-RO-PM
Titre français : Programmation mathématique
Titre anglais : Mathematical Programming
Méta infos : modifiée le : 29/09/2016   par : elloumi   Nb de visiteurs : 256   annee : 3A      periode : 1      Rattachement/module : A      ECTS : 1.5      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : Sourour ELLOUMI,   
Maitres de conférences : Arnaud LAZARE,   

Contenu

a pour prérequis : MAP-RO
MAE41
est prérequis pour : OROC-RO-DM
OROC-RO-MH
Objectifs : Ce cours traite des méthodes de résolution de problèmes d’optimisation
combinatoire fondées sur la programmation mathématique. Après une
introduction générale on montre que de nombreux problèmes de Recherche
Opérationnelle peuvent être modélisés puis résolus à l’aide de la
Programmation Linéaire (PL) où la fonction objectif et les contraintes sont
toutes linéaires et les variables sont continues. Le cours présente les
principes de base de la PL et les principaux algorithmes de résolution.
L’approche par PL fournit également une aide à la résolution de problèmes
plus difficiles (non linéaires, en variables entières,…) en particulier en
fournissant des bornes de la solution optimale. On étudiera les méthodes de
relaxations continues et lagrangiennes ainsi que l'amélioration des bornes par
des méthodes de coupes. Le cours sera illustré par des applications concrètes
(tournées de véhicules, localisation, ordonnancement). Enfin, on abordera la
résolution de problèmes en univers incertain.
Un apprentissage à des logiciels de modélisation et de PL est proposé en TP
puis approfondi dans la réalisation d’un projet.
Mots clés : Optimisation combinatoire, programmation linéaire, relaxation lagrangienne,
génération de colonnes, décomposition.
Objectives : This course presents the methods based on mathematical programming used to solve
many problems of operational research (OR) and combinatorial optimization (CO).
First, a general presentation of OR is given and the main domains of
applications are presented. Then, we show how to modelize a CO problem by a
mathematical program and we study the bases of linear programming and some
algorithms. LP allow to obtain bounds useful to solve more difficult OR problems
(for instance with integer variables) by using continuous or Lagrangean
relaxation methods. The courses are illustrated by several applications like
vehicle routing, localization or scheduling. At the end, we treat the problems
in uncertain environment.
The course includes the presentation of some software of LP and the realization
of a project.
Keywords : Combinatorial optimization, linear programming, Lagrangian relaxation
Supports : Photocopies des vues utilisées en cours.
Lien : http://www.ensta.fr/~diam/ocro,
Biblio : Programmation mathématique - Théorie et algorithmes. M. Minoux. Tec & Doc
(Editions), 2008.
Combinatorial Optimization. W.J. Cook, W.H. Cunningham, W.R. Pulleybank and A.
Schrijver. Wiley, 1998.
Recherche opérationnelle pour ingénieurs. Dominique de Werra , Thomas M.
Liebling , Jean-François Hêche. Presses Polytechniques et Universitaires
Romandes (PPUR) Eyrolles 2003.
Optimisation discrète- De la modélisation à la résolution par les logiciels
de programmation mathématique. Alain Billionnet. Dunod,2007.
Contrôle : Examen et soutenance du projet.

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

mar. 13 sept. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 1 Rappels de PL, Dualité, Programmation en nombres entiers. Exercices
besoin :
Intervenants : Sourour ELLOUMI,
lun. 19 sept. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 2 Modélisation des problèmes par la programmation linéaire en nombres entiers, notion de bonne formulation
besoin :
Intervenants : Sourour ELLOUMI,
lun. 26 sept. 2016   - 8:30 à 12:15 : Bloc de Module en salle Info (MODI)
programme : Séance 3 Prise en main des aspects informatiques Présentation du projet
besoin :
Intervenants : Sourour ELLOUMI,
lun. 03 oct. 2016   - 08:30 à 12:15 : Bloc de Module (1/2 journée) (MOD)
programme : Séance 4 Méthoes de décomposition, Relaxation lagrangienne, génération de colonnes. Exercices
besoin :
Intervenants : Arnaud LAZARE,
lun. 10 oct. 2016   - 08:30 à 12:15 : Bloc de Module en salle Info (MODI)
programme : Séance 5 Point sur le projet Aspects polyédriques de la PLNE : inégalités valides, algorithmes de plans coupants. Exercices.
besoin :
Intervenants : Arnaud LAZARE,
jeu. 20 oct. 2016   - 08:00 à 10:00 : Contrôle (CC)
programme : Séance 6 Contrôle écrit
besoin :
Intervenants : Sourour ELLOUMI,
jeu. 20 oct. 2016   - 10:15 à 12:15 : TD en salle info (TD)
programme : Soutenance de projet
besoin :
Intervenants : Sourour ELLOUMI, Arnaud LAZARE,