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

Solving the simple plant location problem using a data correcting approach

Author

Listed:
  • Goldengorin, Boris

    (Groningen University)

Abstract

The Data Correcting Algorithm is a branch and bound algorithm in which thedata of a given problem instance is ‘corrected’ at each branching in such a waythat the new instance will be as close as possible to a polynomially solvableinstance and the result satisfies an acceptable accuracy (the difference betweenoptimal and current solution). In this paper the data correcting algorithm isapplied to determining exact and approximate optimal solutions to the simpleplant location problem. Implementations of the algorithm are based on apseudo-Boolean representation of the goal function of the SPLP and a newreduction rule. We study the efficiency of the data correcting approach usingtwo different bounds, the combinatorial bound and the Erlenkotter bound. Wepresent computational results on several benchmark instances of the simpleplant location problem, which confirm the efficiency of the data-correcting approach.

Suggested Citation

  • 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).
    • Handle: RePEc:gro:rugsom:01a53
    as

    Download full text from publisher

    File URL: http://irs.ub.rug.nl/ppn/230347045
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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).
    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. repec:dgr:rugsom:00a54 is not listed on IDEAS
    7. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    8. 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)

    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 & 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).
    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. repec:dgr:rugsom:01a53 is not listed on IDEAS
    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. 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.
    7. 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.
    8. 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.
    9. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.
    10. 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.
    11. 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.
    12. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    13. 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.
    14. repec:dgr:rugsom:99a17 is not listed on IDEAS
    15. 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.
    16. 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.
    17. Sharma, R.R.K. & Berry, V., 2007. "Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort," European Journal of Operational Research, Elsevier, vol. 177(2), pages 803-812, March.
    18. R. K. Ahuja & J. B. Orlin & S. Pallottino & M. P. Scaparra & M. G. Scutellà, 2004. "A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem," Management Science, INFORMS, vol. 50(6), pages 749-760, June.
    19. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    20. 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.
    21. Holmberg, Kaj & Ronnqvist, Mikael & Yuan, Di, 1999. "An exact algorithm for the capacitated facility location problems with single sourcing," European Journal of Operational Research, Elsevier, vol. 113(3), pages 544-559, March.
    22. 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.
    23. Jesica Armas & Angel A. Juan & Joan M. Marquès & João Pedro Pedroso, 2017. "Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(10), pages 1161-1176, October.

    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:01a53. 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.