IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v52y2004i4p515-526.html
   My bibliography  Save this article

The Optimal Diversity Management Problem

Author

Listed:
  • 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)

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.

Suggested Citation

  • Olivier Briant & Denis Naddef, 2004. "The Optimal Diversity Management Problem," Operations Research, INFORMS, vol. 52(4), pages 515-526, August.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:4:p:515-526
    DOI: 10.1287/opre.1040.0108
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0108
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0108?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John M. Mulvey & Harlan P. Crowder, 1979. "Cluster Analysis: An Application of Lagrangian Relaxation," Management Science, INFORMS, vol. 25(4), pages 329-340, April.
    2. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    3. Karla L. Hoffman & Manfred Padberg, 1991. "Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 121-134, May.
    4. Ulrich W. Thonemann & Margaret L. Brandeau, 2000. "Optimal Commonality in Component Design," Operations Research, INFORMS, vol. 48(1), pages 1-19, February.
    5. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    6. Beasley, J. E., 1987. "An algorithm for set covering problem," European Journal of Operational Research, Elsevier, vol. 31(1), pages 85-93, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sergio García & Martine Labbé & Alfredo Marín, 2011. "Solving Large p -Median Problems with a Radius Formulation," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 546-556, November.
    2. Sourour Elloumi, 2010. "A tighter formulation of the p-median problem," Journal of Combinatorial Optimization, Springer, vol. 19(1), pages 69-83, January.
    3. Agard, Bruno & Penz, Bernard, 2009. "A simulated annealing method based on a clustering approach to determine bills of materials for a large product family," International Journal of Production Economics, Elsevier, vol. 117(2), pages 389-401, February.
    4. Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    5. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Guimaraes, Renato, 2016. "The component commonality problem in a real multidimensional space: An algorithmic approach," European Journal of Operational Research, Elsevier, vol. 249(1), pages 105-116.
    6. Baud-Lavigne, Bertrand & Agard, Bruno & Penz, Bernard, 2016. "Simultaneous product family and supply chain design: An optimization approach," International Journal of Production Economics, Elsevier, vol. 174(C), pages 111-118.
    7. Bader F. AlBdaiwi & Diptesh Ghosh & Boris Goldengorin, 2011. "Data aggregation for p-median problems," Journal of Combinatorial Optimization, Springer, vol. 21(3), pages 348-363, April.
    8. Baud-Lavigne, Bertrand & Agard, Bruno & Penz, Bernard, 2012. "Mutual impacts of product standardization and supply chain design," International Journal of Production Economics, Elsevier, vol. 135(1), pages 50-60.
    9. Vié, Marie-Sklaerder & Zufferey, Nicolas & Cordeau, Jean-François, 2019. "Solving the Wire-Harness Design Problem at a European car manufacturer," European Journal of Operational Research, Elsevier, vol. 272(2), pages 712-724.
    10. C. Beltran-Royo & J.-P. Vial & A. Alonso-Ayuso, 2012. "Semi-Lagrangian relaxation applied to the uncapacitated facility location problem," Computational Optimization and Applications, Springer, vol. 51(1), pages 387-409, January.
    11. Sáez-Aguado, Jesús & Trandafir, Paula Camelia, 2012. "Some heuristic methods for solving p-median problems with a coverage constraint," European Journal of Operational Research, Elsevier, vol. 220(2), pages 320-327.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    2. Ambros Gleixner & Leona Gottwald & Alexander Hoen, 2023. "P a PILO: A Parallel Presolving Library for Integer and Linear Optimization with Multiprecision Support," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1329-1341, November.
    3. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    4. Robert E. Bixby & Eva K. Lee, 1998. "Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut," Operations Research, INFORMS, vol. 46(3), pages 355-367, June.
    5. R. Lougee-Heimer & W. Adams, 2005. "A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs," Annals of Operations Research, Springer, vol. 139(1), pages 289-320, October.
    6. Patrick Gemander & Wei-Kun Chen & Dieter Weninger & Leona Gottwald & Ambros Gleixner & Alexander Martin, 2020. "Two-row and two-column mixed-integer presolve using hashing-based pairing methods," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 205-240, October.
    7. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    8. Richard Laundy & Michael Perregaard & Gabriel Tavares & Horia Tipi & Alkis Vazacopoulos, 2009. "Solving Hard Mixed-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 304-313, May.
    9. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    10. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1999. "Lifted Cover Inequalities for 0-1 Integer Programs: Complexity," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 117-123, February.
    11. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    12. Tobias Achterberg & Robert E. Bixby & Zonghao Gu & Edward Rothberg & Dieter Weninger, 2020. "Presolve Reductions in Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 473-506, April.
    13. Martin Durbin & Karla Hoffman, 2008. "OR PRACTICE---The Dance of the Thirty-Ton Trucks: Dispatching and Scheduling in a Dynamic Environment," Operations Research, INFORMS, vol. 56(1), pages 3-19, February.
    14. Joshua Q. Hale & Enlu Zhou & Jiming Peng, 2017. "A Lagrangian search method for the P-median problem," Journal of Global Optimization, Springer, vol. 69(1), pages 137-156, September.
    15. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    17. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    18. Yi Zhang & Nikolaos V. Sahinidis & Carlos Nohra & Gang Rong, 2020. "Optimality-based domain reduction for inequality-constrained NLP and MINLP problems," Journal of Global Optimization, Springer, vol. 77(3), pages 425-454, July.
    19. Torbjörn Larsson & Michael Patriksson, 2006. "Global Optimality Conditions for Discrete and Nonconvex Optimization---With Applications to Lagrangian Heuristics and Column Generation," Operations Research, INFORMS, vol. 54(3), pages 436-453, June.
    20. Monique Guignard & Ellis Johnson & Kurt Spielberg, 2005. "Logical Processing for Integer Programming," Annals of Operations Research, Springer, vol. 140(1), pages 263-304, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:52:y:2004:i:4:p:515-526. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.