IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v251y2015icp118-131.html
   My bibliography  Save this article

On a class of subadditive duals for the uncapacitated facility location problem

Author

Listed:
  • Monabbati, Ehsan
  • Kakhki, Hossein Taghizadeh

Abstract

A family of subadditive functions which contains the optimal solution of subadditive duals for integer programs has been presented by Klabjan (2007). In this paper we present a subadditive dual ascent procedure to find an optimal subadditive dual function based on Klabjan’s generator subadditive function. Then we use the proposed method to solve the so called uncapacitated facility location problem (UFLP). Establishing an explicit formulation for generator subadditive functions in the columns of the coefficient matrix of the UFLP, we derive some variable fixing rules for the problem. Some computational results are also presented.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:apmaco:v:251:y:2015:i:c:p:118-131
    DOI: 10.1016/j.amc.2014.10.072
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300314014477
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2014.10.072?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. Resende, Mauricio G.C. & Werneck, Renato F., 2006. "A hybrid multistart heuristic for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 54-68, October.
    2. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    3. Donald Erlenkotter, 1978. "A Dual-Based Procedure for Uncapacitated Facility Location," Operations Research, INFORMS, vol. 26(6), pages 992-1009, December.
    4. 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.
    5. M. A. Efroymson & T. L. Ray, 1966. "A Branch-Bound Algorithm for Plant Location," Operations Research, INFORMS, vol. 14(3), pages 361-368, June.
    6. A. Caprara & J. González, 1996. "A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(1), pages 135-163, June.
    7. 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.
    8. 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.
    9. Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
    10. Klabjan, Diego, 2007. "Subadditive approaches in integer programming," European Journal of Operational Research, Elsevier, vol. 183(2), pages 525-545, December.
    11. Guignard, Monique, 1988. "A Lagrangean dual ascent algorithm for simple plant location problems," European Journal of Operational Research, Elsevier, vol. 35(2), pages 193-200, May.
    12. 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.
    13. Ralph W. Swain, 1974. "A Parametric Decomposition Approach for the Solution of Uncapacitated Location Problems," Management Science, INFORMS, vol. 21(2), pages 189-198, October.
    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.
    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. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    2. Gai, Ling & Liang, Mengpei & Wang, Chenhao, 2024. "Two-facility-location games with mixed types of agents," Applied Mathematics and Computation, Elsevier, vol. 466(C).

    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. 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.
    2. 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.
    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. 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.
    5. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Dong Liang & Wilbert E. Wilhelm, 2013. "Dual‐ascent and primal heuristics for production‐assembly‐distribution system design," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 1-18, February.
    14. 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.
    15. 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.
    16. Resende, Mauricio G.C. & Werneck, Renato F., 2006. "A hybrid multistart heuristic for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 54-68, October.
    17. Fabian Eckert & Costas Arkolakis, 2017. "Combinatorial Discrete Choice," 2017 Meeting Papers 249, Society for Economic Dynamics.
    18. 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).
    19. Abareshi, Maryam & Zaferanieh, Mehdi, 2019. "A bi-level capacitated P-median facility location problem with the most likely allocation solution," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 1-20.
    20. Goldengorin, Boris, 2009. "Maximization of submodular functions: Theory and enumeration algorithms," European Journal of Operational Research, Elsevier, vol. 198(1), pages 102-112, October.

    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:apmaco:v:251:y:2015:i:c:p:118-131. 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: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.