IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v269y2018i3p824-833.html
   My bibliography  Save this article

New valid inequalities and facets for the Simple Plant Location Problem

Author

Listed:
  • Galli, Laura
  • Letchford, Adam N.
  • Miller, Sebastian J.

Abstract

The Simple Plant Location Problem is a well-known (and NP-hard) combinatorial optimisation problem, with applications in logistics. We present a new family of valid inequalities for the associated family of polyhedra, and show that it contains an exponentially large number of new facet-defining members. We also present a new procedure, called facility augmentation, which enables one to derive even more valid and facet-defining inequalities.

Suggested Citation

  • Galli, Laura & Letchford, Adam N. & Miller, Sebastian J., 2018. "New valid inequalities and facets for the Simple Plant Location Problem," European Journal of Operational Research, Elsevier, vol. 269(3), pages 824-833.
    • Handle: RePEc:eee:ejores:v:269:y:2018:i:3:p:824-833
    DOI: 10.1016/j.ejor.2018.03.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718302182
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.03.009?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ghosh, Diptesh, 2003. "Neighborhood search heuristics for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 150(1), pages 150-162, October.
    2. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    3. D. Chinhyung Cho & Manfred W. Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 590-612, November.
    4. Vedat Verter, 2011. "Uncapacitated and Capacitated Facility Location Problems," International Series in Operations Research & Management Science, in: H. A. Eiselt & Vladimir Marianov (ed.), Foundations of Location Analysis, chapter 0, pages 25-37, Springer.
    5. 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.
    6. D. Chinhyung Cho & Ellis L. Johnson & Manfred Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 579-589, November.
    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. Prodromos Chatzoglou & Dimitrios Chatzoudes & Zografia Petrakopoulou & Elena Polychrou, 2018. "Plant location factors: a field research," OPSEARCH, Springer;Operational Research Society of India, vol. 55(3), pages 749-786, November.
    2. Michael J. Brusco, 2022. "Solving Classic Discrete Facility Location Problems Using Excel Spreadsheets," INFORMS Transactions on Education, INFORMS, vol. 22(3), pages 160-171, May.
    3. Xinxin Wang & Zeshui Xu & Yong Qin, 2022. "Structure, trend and prospect of operational research: a scientific analysis for publications from 1952 to 2020 included in Web of Science database," Fuzzy Optimization and Decision Making, Springer, vol. 21(4), pages 649-672, December.

    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. 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.
    2. Matteo Fischetti & Ivana Ljubić & Markus Sinnl, 2017. "Redesigning Benders Decomposition for Large-Scale Facility Location," Management Science, INFORMS, vol. 63(7), pages 2146-2162, July.
    3. 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.
    4. Alessandro Agnetis & Arianna Alfieri & Gaia Nicosia, 2009. "Single-Machine Scheduling Problems with Generalized Preemption," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 1-12, February.
    5. 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.
    6. J Brimberg & P Hansen & G Laporte & N Mladenović & D Urošević, 2008. "The maximum return-on-investment plant location problem with market share," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 399-406, March.
    7. 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.
    8. Enrique Domínguez & Alfredo Marín, 2020. "Discrete ordered median problem with induced order," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 793-813, October.
    9. M T Ramos & J Sáez, 2005. "Solving capacitated facility location problems by Fenchel cutting planes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 297-306, March.
    10. Fabian Eckert & Costas Arkolakis, 2017. "Combinatorial Discrete Choice," 2017 Meeting Papers 249, Society for Economic Dynamics.
    11. Marianov, Vladimir & Eiselt, H.A. & Lüer-Villagra, Armin, 2018. "Effects of multipurpose shopping trips on retail store location in a duopoly," European Journal of Operational Research, Elsevier, vol. 269(2), pages 782-792.
    12. Francisco Casas & Claudio E. Torres & Ignacio Araya, 2022. "A heuristic search based on diversity for solving combinatorial problems," Journal of Heuristics, Springer, vol. 28(3), pages 287-328, 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. 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.
    15. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    16. Pelegrín, Mercedes, 2023. "New variants of the simple plant location problem and applications," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1094-1108.
    17. 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.
    18. 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.
    19. Hee-Su Hwang & Siriwat Visoldilokpun & Jay M. Rosenberger, 2008. "A Branch-and-Price-and-Cut Method for Ship Scheduling with Limited Risk," Transportation Science, INFORMS, vol. 42(3), pages 336-351, August.
    20. Alexander Bockmayr & Thomas Kasper, 1998. "Branch and Infer: A Unifying Framework for Integer and Finite Domain Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 10(3), pages 287-300, August.

    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:eee:ejores:v:269:y:2018:i:3:p:824-833. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.