US331C

Programmation mathématique


3 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

Cours d'introduction à la Recherche Opérationnelle

Objectifs pédagogiques

Tour d'horizon des concepts fondamentaux en optimisation discrète

Compétences

Ce cours vise à compléter les connaissances de base introduites en M1 et à se familiariser avec les modèles et concepts classiques de l'optimisation discrète. Il vise aussi à faire connaître les constituants de base d'un solveur moderne de programmes linéaires ou quadratiques en nombres entiers.

Contenu

  • Efficacité de Résolution des PLNE 1

    Branch-and-Bound, algorithme dual du simplexe et son utilisation dans le Branch-and-Bound. Autres ingrédients d'un Branch-and-Bound (prétraitement, heuristiques, ...)

  • Efficacité de Résolution des PLNE 2

    Méthodes de coupes. Notion d'inégalité valide, Résolution des PLNE par les coupes de Gomory et leur mise en œuvre utilisant le simplexe dual. Branch-and-cut et quelques illustrations par les solveurs modernes. Mini-TP de modélisation en Julia Gurobi ?

  • Modèles classiques de PLNE et notion de bonne formulation

    Revue de problèmes classiques et de leurs formulations. Existence de plusieurs formulations d'un même problème. Notion de formulation idéale. Critère de comparaison des formulations. Modélisation par un nombre exponentiel de variables ou de contraintes. Problème de séparation.

  • Introduction à l'optimisation quadratique en variables binaires

    Fonctions pseudobooléennes et posiformes quadratiques. Cas polynomiaux. Linéarisations et convexifications usuelles. Comportement des solveurs standard.

  • Introduction aux méthodes de point intérieur en programmation linéaire

    Notion de chemin central et de barrière logarithmique. Schéma des méthodes primales-duales. Implémentation simple en Matlab ou Julia. MPI dans les solveurs standard. Extention au cas quadratique convexe.

Modalités de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003