Objectifs de la formation

Appréhender le caractère discret d’un problème de décision à l’aide de la Programmation Linéaire en Nombres Entiers (PLNE).

Pour qui ?

Ingénieurs, scientifiques et développeurs intéressés par la modélisation de problèmes de décision et la mise en œuvre d’algorithmes d’optimisation.

Programmation linéaire en nombres entiers (PLNE)
• Rappels de programmation linéaire.
• Formulations : Qu’est-ce qu’un programme en nombres entiers ? Formulation d’un programme en nombres entiers. L’explosion combinatoire. Formulations PLNE. Formulations alternatives.
• Optimalité, relaxations et bornes : optimalité et relaxation, relaxations linéaires, relaxations combinatoires, relaxation lagrangienne, dualité, bornes primales.
• Techniques de modélisation et illustrations.
• Résolution de programmes linéaires en nombres entiers par Branch-and-Bound.
• Principes des méthodes de coupes et de Branch-and-Cut. Traitement d’exemples numériques.

Mise en œuvre
• Présentation, modélisation et résolution d’un problème de voyageur de commerce avec le solveur FICO® Xpress.
• Présentation, modélisation et résolution d’un problème industriel avec FICO® Xpress.
• Confrontation d’une formulation naïve du problème et d’une formulation intégrant des coupes.

Introduction aux méthodes de décomposition
• Introduction aux méthodes de décomposition : illustration de l’intérêt de la génération de colonnes.
• Principes et intérêt pratique des techniques de génération de colonnes.
• Présentation d’une application industrielle.