Description

Les problèmes de localisation représentent une importante classe de problèmes fréquemment rencontrés dans les entreprises : comment répartir des "objets"  sur des "sites" en respectant des contraintes données, comme par exemple les capacités maximales de chaque site, et en répondant au mieux aux objectifs fixés, par exemple la minimisation des coûts ou l'équilibrage des charges entre les sites. Les objets peuvent être des entrepôts, des bases de données, des modules de programmes, des concentrateurs téléphoniques,.. et les sites, des villes, des processeurs, .. Les variables sont ici définies dans le domaine du 0-1, c'est-à-dire que l'on doit décider de placer ou non un objet sur un site. Les objectifs s'expriment par une fonction mathématique linéaire ou quadratique généralement bi-critère. Le cours a pour objectif de présenter, à partir de ces problèmes concrets difficiles, la conduite de bout en bout d'une étude d'optimisation combinatoire dans le domaine discret, de présenter la plus grande partie des outils de résolution disponibles et les progrès envisageables dans les années futures.

Présentation des problèmes théoriques de base et de plusieurs applications industrielles.

- Modélisation des problèmes : les enjeux d'un bon modèle.

- Calculs de bornes: méthodes de coupe, relaxation lagrangienne, méthodes de décomposition.

- Approximation : résultats théoriques a priori et résolution par heuristiques avec garantie.

- Résolution exacte par méthodes spécifiques ou utilisation de logiciels généralistes.

- Etude de cas particuliers polynomiaux.