Objectifs : Plusieurs problèmes concrets issus de domaines divers peuvent être formulés comme des programmes linéaires et des programmes linéaires en nombres entiers. Le but de ce module est d'étudier la modélisation et les méthodes de résolution de ces problèmes, basées sur la programmation linéaire et la programmation en nombres entiers. On introduit les principaux outils théoriques et algorithmiques nécessaires à la compréhension de ces méthodes, et on présente certaines applications réelles illustrant les algorithmes étudiés.

Contenu :

• Modèles de programmes en nombres entiers

• Relation entre problèmes combinatoires et programmation linéaire

• Séparation et optimisation

• Méthode de coupe

• Techniques de décomposition

• Applications

Bibliographie.

• W. Cook, W. Cunningham, W.R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", Wiley (1997).

• G. L. Nemhauser and L. A. Wolsey, " Integer and Combinatorial Optimization", Wiley (1988).

• L. A. Wolsey, Integer Programmation, Wiley (1998).

• A. Schrijver, "Theory of Linear and Integer Programming", Wiley (1998).