Programmation mathématique

Code UE : US331C

  • Cours
  • 4 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Christophe PICOULEAU

Compétences visées

Capacité à modéliser un problème d'optimisation discrète ou mixte par la programmation mathématique. Connaissance des principales méthodes permettant de le résoudre.

Contenu

Dans une première partie, on montrera comment aborder par la programmation mathématique les problèmes d'optimisation combinatoire que l'on rencontre dans de nombreux domaines d'applications. On présentera différentes méthodes de résolution en insistant sur la phase de modélisation. On introduira dans une deuxième partie les méthodes dites polyédriques qui fournissent un cadre général et efficace pour la résolution de ces problèmes. Cette méthodologie a été à l'origine de progrès importants en optimisation combinatoire. La troisième partie du cours est une initiation à la programmation semi-définie qui est un cas particulier de la programmation convexe. La SDP permet d'obtenir des bornes de très bonne qualité pour de nombreux problèmes d'optimisation combinatoires difficiles et est également à la base d'heuristiques efficaces pour ces problèmes. Contenu détaillé : Modélisation, choix d'une formulation, exemples concrets. Programmation linéaire et non linéaire en nombres entiers, prétraitements. Dualité et décomposition lagrangienne. Réductions, linéarisations, relaxations convexes. Notions essentielles relatives à la description des polyèdres. Inégalités valides en programmation linéaire en nombres entiers. Coupes de Chvatal-Gomory. Le problème de séparation. Application au problème du voyageur de commerce. Quelques rappels sur les matrices positives, formes primale et duale d'un programme semi-défini. Modélisation et étude de plusieurs problèmes d'optimisation combinatoire.

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Type
Intitulé
Equipe pédagogique
Modalité(s) / Lieu(x)
Code
Equipe pédagogique Informatique
Modalité(s) / Lieu(x)
  • - Enseignée en formation présentielle et/ou partiellement à distance : Paris
  • Type Intitulé Equipe pédagogique Modalité(s) / Lieu(x) Code

    Contact

    Recherche opérationnelle
    2D4P20, 33-1-10, 2 rue Conté
    75003 Paris
    Tel :01 40 27 22 67
    secretariat.ro@cnam.fr

    Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

    Enseignement non programmé en 2017/2018