Denis Naddef
University of Grenoble, also Tepper School of Business
Friday, April 29
2:00 - 3:30 pm
384 Posner Hall
The Diversity Management Problem
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 in choosing an optimal set of some given number
k of configurations that will be produced, any non produced configuration
being replaced by the cheapest produced one 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
talk deals with the use of Lagrangian Relaxation to reduce the size of the
problem in order to be able subsequently to solve it to optimality via
classical integer optimization.
Joint work with Olivier Briant.
