This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Briant, O. Articles by Naddef, D. Search for Related Content

The Optimal Diversity Management Problem

Laboratoire Mathématiques Appliquées de Bordeaux, 351 cours de la libération, 33405 Talence, France
Laboratoire Informatique et Distribution—IMAG, Institut National Polythechnique de Grenoble, 51 avenue Jean Kuntzmann, 38330 Montbonnot, France
olivier.briant{at}math.u-bordeaux.fr
denis.naddef{at}imag.fr

In some industries, a certain part can be needed in a very large number of different configurations. This is the case, e.g., for the electrical wirings in European car factories. A given configuration can be replaced by a more complete, therefore more expensive, one. The diversity management problem consists of choosing an optimal set of some given number k of configurations that will be produced, any nonproduced configuration being replaced by the cheapest produced one that is compatible with it. We model the problem as an integer linear program. Our aim is to solve those problems to optimality. The large-scale instances we are interested in lead to difficult LP relaxations, which seem to be intractable by the best direct methods currently available. Most of this paper deals with the use of Lagrangean relaxation to reduce the size of the problem in order to be able, subsequently, to solve it to optimality via classical integer optimization.

Subject classifications: large-scale integer programming and relaxations; Lagrangean relaxation of a large linear integer program arising from an application; production planning; choice of production.
History: Received May 2000; revision received May 2002; revision received January 2003; accepted June 2003.