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. Charles S. Revelle & Gilbert Laporte, 1996. "The Plant Location Problem: New Models and Research Prospects," Operations Research, INFORMS, vol. 44(6), pages 864-874, December.
    2. 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.
    3. 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).
    4. Donald Erlenkotter, 1978. "A Dual-Based Procedure for Uncapacitated Facility Location," Operations Research, INFORMS, vol. 26(6), pages 992-1009, December.
    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. repec:dgr:rugsom:00a54 is not listed on IDEAS
    8. Philip C. Jones & Timothy J. Lowe & Georg Muller & Ning Xu & Yinyu Ye & James L. Zydiak, 1995. "Specially Structured Uncapacitated Facility Location Problems," Operations Research, INFORMS, vol. 43(4), pages 661-669, August.
    9. 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.
    10. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    11. VAN ROY, Tony J. & WOLSEY, Laurence A., 1986. "Valid inequalities for mixed 0-1 programs," LIDAM Reprints CORE 697, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. 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. 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. Buchheim, Christoph & Crama, Yves & Rodríguez-Heck, Elisabeth, 2019. "Berge-acyclic multilinear 0–1 optimization problems," European Journal of Operational Research, Elsevier, vol. 273(1), pages 102-107.
    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.
    4. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    5. Jaroslav Janáček & Ľuboš Buzna, 2008. "An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem," Annals of Operations Research, Springer, vol. 164(1), pages 97-109, November.
    6. 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.
    7. 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.
    8. 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).

    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. 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. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    3. 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.
    4. repec:dgr:rugsom:01a14 is not listed on IDEAS
    5. 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.
    6. repec:dgr:rugsom:01a53 is not listed on IDEAS
    7. Kurt Jörnsten & Andreas Klose, 2016. "An improved Lagrangian relaxation and dual ascent approach to facility location problems," Computational Management Science, Springer, vol. 13(3), pages 317-348, July.
    8. Monabbati, Ehsan & Kakhki, Hossein Taghizadeh, 2015. "On a class of subadditive duals for the uncapacitated facility location problem," Applied Mathematics and Computation, Elsevier, vol. 251(C), pages 118-131.
    9. 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.
    10. 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).
    11. Hinojosa, Y. & Puerto, J. & Fernandez, F. R., 2000. "A multiperiod two-echelon multicommodity capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 271-291, June.
    12. H K Smith & G Laporte & P R Harper, 2009. "Locational analysis: highlights of growth to maturity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 140-148, May.
    13. repec:dgr:rugsom:00a54 is not listed on IDEAS
    14. Dupont, Lionel, 2008. "Branch and bound algorithm for a facility location problem with concave site dependent costs," International Journal of Production Economics, Elsevier, vol. 112(1), pages 245-254, March.
    15. Jayaraman, Vaidyanathan & Pirkul, Hasan, 2001. "Planning and coordination of production and distribution facilities for multiple commodities," European Journal of Operational Research, Elsevier, vol. 133(2), pages 394-408, January.
    16. Barros, Lilian & Riley, Michael, 2001. "A combinatorial approach to level of repair analysis," European Journal of Operational Research, Elsevier, vol. 129(2), pages 242-251, March.
    17. Letchford, Adam N. & Miller, Sebastian J., 2014. "An aggressive reduction scheme for the simple plant location problem," European Journal of Operational Research, Elsevier, vol. 234(3), pages 674-682.
    18. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    19. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    20. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    21. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    22. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    23. Holmberg, Kaj & Ling, Jonas, 1997. "A Lagrangean heuristic for the facility location problem with staircase costs," European Journal of Operational Research, Elsevier, vol. 97(1), pages 63-74, February.

    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.

    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: Hanneke Tamling (email available below). General contact details of provider: https://edirc.repec.org/data/ferugnl.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.