Contenu
Préparer les étudiants à aborder les problèmes d'optimisation discrète que l'on rencontre dans de nombreux domaines d'applications. Les différentes phases d'un projet seront examinées : formulation du problème, construction d'un modèle mathématique, résolution du modèle et mise en œuvre informatique, étude de la solution obtenue. On introduira également les méthodes dites polyédriques qui fournissent un cadre assez général fondé sur la recherche d'inégalités valides pour la résolution de problèmes d'optimisation combinatoire. Cette méthodologie a été à l'origine de progrès importants réalisés sur le traitement de problèmes fondamentaux comme celui du Voyageur de commerce. L'objectif du cours est de faire comprendre les caractéristiques de l'approche, de présenter les descriptions polyédriques complètes de certains problèmes et les principales méthodes de recherche d'inégalités valides, et de montrer à travers certains problèmes phares l'efficacité de ces méthodes.
|
