Programmation mathématique
4 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours
Publié Du 01-09-2011 au 31-08-2024
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.
L'unité US331C apparaît dans 1 cursus.
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.