IDEAS home Printed from https://ideas.repec.org/p/gro/rugsom/01a14.html
   My bibliography  Save this paper

Branch and peg algorithms for the simple plant location problem

Author

Listed:
  • Goldengorin, Boris
  • Ghosh, Diptesh
  • Sierksma, Gerard

    (Groningen University)

Abstract

The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem of ten appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present a few techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to assigning values to variables outside the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10% of the execution times required by branch and bound algorithms.

Suggested Citation

  • Goldengorin, Boris & Ghosh, Diptesh & Sierksma, Gerard, 2001. "Branch and peg algorithms for the simple plant location problem," Research Report 01A14, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
  • Handle: RePEc:gro:rugsom:01a14
    as

    Download full text from publisher

    File URL: http://irs.ub.rug.nl/ppn/21798391X
    Download Restriction: no

    References listed on IDEAS

    as
    1. Boris Goldengorin & Gerard Sierksma & Gert A. Tijssen & Michael Tso, 1999. "The Data-Correcting Algorithm for the Minimization of Supermodular Functions," Management Science, INFORMS, vol. 45(11), pages 1539-1551, November.
    2. Ghosh, Diptesh & Sierksma, Gerard & Goldengorin, Boris & AlMohammad, Bader F., 2000. "Equivalent instances of the simple plant location problem," Research Report 00A54, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    3. Krarup, Jakob & Pruzan, Peter Mark, 1983. "The simple plant location problem: Survey and synthesis," European Journal of Operational Research, Elsevier, vol. 12(1), pages 36-57, January.
    4. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    5. Gerard Cornuejols & Marshall L. Fisher & George L. Nemhauser, 1977. "Exceptional Paper--Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," Management Science, INFORMS, vol. 23(8), pages 789-810, April.
    6. P. M. Dearing & P. L. Hammer & B. Simeone, 1992. "Boolean and Graph Theoretic Formulations of the Simple Plant Location Problem," Transportation Science, INFORMS, vol. 26(2), pages 138-148, May.
    7. R. S. Garfinkel & A. W. Neebe & M. R. Rao, 1974. "An Algorithm for the M-Median Plant Location Problem," Transportation Science, INFORMS, vol. 8(3), pages 217-236, August.
    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. Goldengorin, Boris, 2001. "Solving the simple plant location problem using a data correcting approach," Research Report 01A53, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    2. Rafael Pastor & Albert Corominas, 2004. "Branch and win: OR tree search algorithms for solving combinatorial optimisation problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 169-191, June.
    3. M. Neema & K. Maniruzzaman & A. Ohgai, 2011. "New Genetic Algorithms Based Approaches to Continuous p-Median Problem," Networks and Spatial Economics, Springer, vol. 11(1), pages 83-99, March.

    More about this item

    Statistics

    Access and download statistics

    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:gro:rugsom:01a14. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Hanneke Tamling). General contact details of provider: http://edirc.repec.org/data/ferugnl.html .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.