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

Minimum Spanning Trees with neighborhoods: Mathematical programming formulations and solution methods

Author

Listed:
  • Blanco, Víctor
  • Fernández, Elena
  • Puerto, Justo

Abstract

This paper studies Minimum Spanning Trees under incomplete information assuming that it is only known that vertices belong to some neighborhoods that are second order cone representable and distances are measured with a ℓq-norm. Two Mixed Integer Non Linear mathematical programming formulations are presented, based on alternative representations of subtour elimination constraints. A solution scheme is also proposed, resulting from a reformulation suitable for a Benders-like decomposition, which is embedded within an exact branch-and-cut framework. Furthermore, a mathheuristic is developed, which alternates in solving convex subproblems in different solution spaces, and is able to solve larger instances. The results of extensive computational experiments are reported and analyzed.

Suggested Citation

  • Blanco, Víctor & Fernández, Elena & Puerto, Justo, 2017. "Minimum Spanning Trees with neighborhoods: Mathematical programming formulations and solution methods," European Journal of Operational Research, Elsevier, vol. 262(3), pages 863-878.
    • Handle: RePEc:eee:ejores:v:262:y:2017:i:3:p:863-878
    DOI: 10.1016/j.ejor.2017.04.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717303569
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.04.023?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. Stefan Nickel & Justo Puerto & Antonio M. Rodriguez-Chia, 2003. "An Approach to Location Models Involving Sets as Existing Facilities," Mathematics of Operations Research, INFORMS, vol. 28(4), pages 693-715, November.
    2. Jochen Gorski & Frank Pfeuffer & Kathrin Klamroth, 2007. "Biconvex sets and optimization with biconvex functions: a survey and extensions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(3), pages 373-407, December.
    3. H. Frank, 1969. "Shortest Paths in Probabilistic Graphs," Operations Research, INFORMS, vol. 17(4), pages 583-599, August.
    4. Richard E. Wendell & Arthur P. Hurter, 1976. "Minimization of a Non-Separable Objective Function Subject to Disjoint Constraints," Operations Research, INFORMS, vol. 24(4), pages 643-657, August.
    5. Victor Blanco & Justo Puerto & Safae El Haj Ben Ali, 2014. "Revisiting several problems and algorithms in continuous location with $$\ell _\tau $$ ℓ τ norms," Computational Optimization and Applications, Springer, vol. 58(3), pages 563-595, July.
    6. Bertsimas, Dimitris & Howell, Louis H., 1993. "Further results on the probabilistic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 65(1), pages 68-95, February.
    7. Henrik Juel, 1981. "Technical Note—Bounds in the Generalized Weber Problem under Locational Uncertainty," Operations Research, INFORMS, vol. 29(6), pages 1219-1227, December.
    8. Fischetti, Matteo & Ljubić, Ivana & Sinnl, Markus, 2016. "Benders decomposition without separability: A computational study for capacitated facility location problems," European Journal of Operational Research, Elsevier, vol. 253(3), pages 557-569.
    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. I. Espejo & R. Páez & J. Puerto & A. M. Rodríguez-Chía, 2022. "Minimum cost b-matching problems with neighborhoods," Computational Optimization and Applications, Springer, vol. 83(2), pages 525-553, November.
    2. Puerto, Justo & Valverde, Carlos, 2022. "Routing for unmanned aerial vehicles: Touring dimensional sets," European Journal of Operational Research, Elsevier, vol. 298(1), pages 118-136.
    3. Weinand, Jann Michael & Kleinebrahm, Max & McKenna, Russell & Mainzer, Kai & Fichtner, Wolf, 2019. "Developing a combinatorial optimisation approach to design district heating networks based on deep geothermal energy," Applied Energy, Elsevier, vol. 251(C), pages 1-1.

    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. Víctor Blanco, 2019. "Ordered p-median problems with neighbourhoods," Computational Optimization and Applications, Springer, vol. 73(2), pages 603-645, June.
    2. Dimitris Bertsimas & Xuan Vinh Doan & Karthik Natarajan & Chung-Piaw Teo, 2010. "Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 580-602, August.
    3. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    4. Thomas Kleinert & Martin Schmidt, 2021. "Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 198-215, January.
    5. Skripnikov, A. & Michailidis, G., 2019. "Regularized joint estimation of related vector autoregressive models," Computational Statistics & Data Analysis, Elsevier, vol. 139(C), pages 164-177.
    6. Carina Moreira Costa & Dennis Kreber & Martin Schmidt, 2022. "An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 2968-2988, November.
    7. Björn Geißler & Antonio Morsi & Lars Schewe & Martin Schmidt, 2018. "Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 309-323, May.
    8. Nazlı Dolu & Umur Hastürk & Mustafa Kemal Tural, 2020. "Solution methods for a min–max facility location problem with regional customers considering closest Euclidean distances," Computational Optimization and Applications, Springer, vol. 75(2), pages 537-560, March.
    9. Lin, Yun Hui & Wang, Yuan & He, Dongdong & Lee, Loo Hay, 2020. "Last-mile delivery: Optimal locker location under multinomial logit choice model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    10. C. Valero Franco & A. Rodríguez-Chía & I. Espejo Miranda, 2008. "The single facility location problem with average-distances," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 16(1), pages 164-194, July.
    11. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    12. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    13. Ma, Shujie & Linton, Oliver & Gao, Jiti, 2021. "Estimation and inference in semiparametric quantile factor models," Journal of Econometrics, Elsevier, vol. 222(1), pages 295-323.
    14. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    15. André Berger & Alexander Grigoriev & Andrej Winokurow, 2017. "An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions," Computational Optimization and Applications, Springer, vol. 68(3), pages 661-669, December.
    16. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    17. Bi Chen & William Lam & Agachai Sumalee & Qingquan Li & Hu Shao & Zhixiang Fang, 2013. "Finding Reliable Shortest Paths in Road Networks Under Uncertainty," Networks and Spatial Economics, Springer, vol. 13(2), pages 123-148, June.
    18. Yueyue Fan & Yu Nie, 2006. "Optimal Routing for Maximizing the Travel Time Reliability," Networks and Spatial Economics, Springer, vol. 6(3), pages 333-344, September.
    19. Yang, Yongjian & Yin, Yunqiang & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Dhamotharan, Lalitha, 2023. "Distributionally robust multi-period location-allocation with multiple resources and capacity levels in humanitarian logistics," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1042-1062.
    20. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.

    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:262:y:2017:i:3:p:863-878. 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.