The Optimal Diversity Management Problem

Olivier Briant () and Denis Naddef ()
Additional contact information
Olivier Briant: Laboratoire Mathématiques Appliquées de Bordeaux, 351 cours de la libération, 33405 Talence, France
Denis Naddef: Laboratoire Informatique et Distribution---IMAG, Institut National Polythechnique de Grenoble, 51 avenue Jean Kuntzmann, 38330 Montbonnot, France

Operations Research, 2004, vol. 52, issue 4, 515-526

Abstract: 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.

Keywords: large-scale integer programming and relaxations; Lagrangean relaxation of a large linear integer program arising from an application; production planning; choice of production (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0108 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:4:p:515-526

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().