Description

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 oeuvre 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.

Modélisation de problèmes d'optimisation discrets, choix d une formulation, programmation linéaire en nombres entiers et en variables mixtes (procédures par séparation et évaluation, méthodes de coupes), dualité et décomposition lagrangienne, programmation non linéaire en variables bivalentes et programmation non linéaire en variables mixtes, réductions, linéarisations, relaxations convexes. L'approche polyédrique générale. Inégalités valides en programmation linéaire en nombres entiers. Coupes de Chvatal-Gomory. Le problème de séparation. Le problème du voyageur de commerce.