Theoretical and computational studies of the diversity management problem
Étude théorique et numérique du problème de la gestion de la diversité
Résumé
The diversity management problem is defined on a partially ordered set. The objective is to produce a subset of $k$ reference elements, $k$ being a given number, while minimizing the cost. Demands and unit costs of production are known. Each non produced element must be replaced by a reference which is higher in the partial order, and this implies an overcost. After a theoretical study on the complexity of this problem, we describe and justify the model we chose. This model is an integer linear program close to that commonly used for the $k$-median problem. To solve this program, we present a Lagrangean approach, and various criteria of variable fixing. We exploit also this approach to build feasible solutions of good quality. Finally, we design a Branch and Cut type algorithm to solve our problem to optimality. To do so, we first do a polyhedral study of the convex hull of the solutions. We present a particular type of cuts that eliminate fractional solutions, as well as a heuristic to generate them. We conclude by numerical tests carried out on real world instances.
Le problème de la gestion de la diversité est défini sur un ensemble partiellement ordonné d'élements possédant des demandes et des coûts unitaires de production. L'objectif est de produire un sous-ensemble de $k$ éléments références, $k$ étant un nombre donné, minimisant les coûts. Chaque élément non produit doit être remplacé par une référence qui lui est supérieure, ce qui implique un sur-coût. Après une étude théorique de complexité, nous modélisons ce problème grâce à un programme linéaire en nombres entiers, proche de ceux des problèmes de localisation $k$-médians. Pour résoudre ce programme, nous présentons un algorithme lagrangien, ainsi que de nombreux critères de fixation de variables permettant de réduire la taille du problème. Nous exploitons ensuite cet algorithme pour construire des solutions de bonne qualité. Nous développons enfin un algorithme exact de Séparation et Coupe. Nous étudions un certain type de coupes ainsi qu'une heuristique permettant de les générer. Nous concluons par des tests numériques effectués sur des instances réelles.
Loading...