The optimal diversity management problem

• 成果类型: Article
• 署名作者: Briant, O; Naddef, D
• 署名单位: Universite de Bordeaux; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1040.0108
• 发表日期: 2004
• 页码: 515-526
• 关键词: large-scale integer programming and relaxations : Lagrangean relaxation of a large linear integer program arising from an application; production planning : choice of production

摘要

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.