Programmation mathématique
Sessions de formation
(Fuseau horaire : Europe/Paris)
Aucune session n'est visible pour le moment
Présentation
Public, conditions d'accès et prérequis
Cours d'introduction à la Recherche Opérationnelle
Objectifs
Tour d'horizon des concepts fondamentaux en optimisation discrète
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 d'évaluation
- Examen final