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

Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem

Author

Listed:
  • Fernández, Elena
  • Pozo, Miguel A.
  • Puerto, Justo
  • Scozzari, Andrea

Abstract

Multiobjective Spanning Tree Problems are studied in this paper. The ordered median objective function is used as an averaging operator to aggregate the vector of objective values of feasible solutions. This leads to the Ordered Weighted Average Spanning Tree Problem, a nonlinear combinatorial optimization problem. Different mixed integer linear programs are proposed, based on the most relevant minimum cost spanning tree models in the literature. These formulations are analyzed and several enhancements presented. Their empirical performance is tested over a set of randomly generated benchmark instances. The results of the computational experiments show that the choice of an appropriate formulation allows to solve larger instances with more objectives than those previously solved in the literature.

Suggested Citation

  • Fernández, Elena & Pozo, Miguel A. & Puerto, Justo & Scozzari, Andrea, 2017. "Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem," European Journal of Operational Research, Elsevier, vol. 260(3), pages 886-903.
    • Handle: RePEc:eee:ejores:v:260:y:2017:i:3:p:886-903
    DOI: 10.1016/j.ejor.2016.10.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716308499
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.10.016?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. Pierre Hansen & Martine Labbé, 1988. "Algorithms for Voting and Competitive Location on a Network," Transportation Science, INFORMS, vol. 22(4), pages 278-288, November.
    2. Egon Balas & Manfred W. Padberg, 1972. "On the Set-Covering Problem," Operations Research, INFORMS, vol. 20(6), pages 1152-1161, December.
    3. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    4. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    5. Eugene L. Lawler, 1972. "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem," Management Science, INFORMS, vol. 18(7), pages 401-405, March.
    6. Francis Sourd & Olivier Spanjaard, 2008. "A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 472-484, August.
    7. Igor Averbakh & Oded Berman, 1995. "Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree," Transportation Science, INFORMS, vol. 29(2), pages 184-197, May.
    8. Justo Puerto, 2008. "A New Formulation of the Capacitated Discrete Ordered Median Problems with {0, 1}-Assignment," Operations Research Proceedings, in: Jörg Kalcsics & Stefan Nickel (ed.), Operations Research Proceedings 2007, pages 165-170, Springer.
    9. Ramos, R. M. & Alonso, S. & Sicilia, J. & Gonzalez, C., 1998. "The problem of the optimal biobjective spanning tree," European Journal of Operational Research, Elsevier, vol. 111(3), pages 617-628, December.
    10. Ogryczak, Wlodzimierz & Sliwinski, Tomasz, 2003. "On solving linear programs with the ordered weighted averaging objective," European Journal of Operational Research, Elsevier, vol. 148(1), pages 80-91, July.
    11. Galand, Lucie & Perny, Patrice & Spanjaard, Olivier, 2010. "Choquet-based optimisation in multiobjective shortest path and spanning tree problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 303-315, July.
    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. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2020. "Approximating combinatorial optimization problems with the ordered weighted averaging criterion," European Journal of Operational Research, Elsevier, vol. 286(3), pages 828-838.
    2. 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.
    3. Francesco Cesarone & Justo Puerto, 2024. "New approximate stochastic dominance approaches for Enhanced Indexation models," Papers 2401.12669, arXiv.org.
    4. Hui-Chin Tang & Shen-Tai Yang, 2018. "Optimizing Three-Dimensional Constrained Ordered Weighted Averaging Aggregation Problem with Bounded Variables," Mathematics, MDPI, vol. 6(9), pages 1-16, September.

    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. Elena Fernández & Justo Puerto & Antonio Rodríguez-Chía, 2013. "On discrete optimization with ordering," Annals of Operations Research, Springer, vol. 207(1), pages 83-96, August.
    2. Pascoal, Marta M.B. & Sedeño-Noda, Antonio, 2012. "Enumerating K best paths in length order in DAGs," European Journal of Operational Research, Elsevier, vol. 221(2), pages 308-316.
    3. I. F. C. Fernandes & E. F. G. Goldbarg & S. M. D. M. Maia & M. C. Goldbarg, 2020. "Empirical study of exact algorithms for the multi-objective spanning tree," Computational Optimization and Applications, Springer, vol. 75(2), pages 561-605, March.
    4. Cristina Requejo & Eulália Santos, 2020. "Efficient lower and upper bounds for the weight-constrained minimum spanning tree problem using simple Lagrangian based algorithms," Operational Research, Springer, vol. 20(4), pages 2467-2495, December.
    5. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.
    6. Guazzelli, Cauê Sauter & Cunha, Claudio B., 2018. "Exploring K-best solutions to enrich network design decision-making," Omega, Elsevier, vol. 78(C), pages 139-164.
    7. Sébastien Giguère & François Laviolette & Mario Marchand & Denise Tremblay & Sylvain Moineau & Xinxia Liang & Éric Biron & Jacques Corbeil, 2015. "Machine Learning Assisted Design of Highly Active Peptides for Drug Discovery," PLOS Computational Biology, Public Library of Science, vol. 11(4), pages 1-21, April.
    8. Ehrgott, Matthias & Skriver, Anders J. V., 2003. "Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach," European Journal of Operational Research, Elsevier, vol. 147(3), pages 657-664, June.
    9. Antonio Sedeño-Noda, 2016. "Ranking One Million Simple Paths in Road Networks," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-20, October.
    10. Andréa Santos & Diego Lima & Dario Aloise, 2014. "Modeling and solving the bi-objective minimum diameter-cost spanning tree problem," Journal of Global Optimization, Springer, vol. 60(2), pages 195-216, October.
    11. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    12. Pushak, Yasha & Hare, Warren & Lucet, Yves, 2016. "Multiple-path selection for new highway alignments using discrete algorithms," European Journal of Operational Research, Elsevier, vol. 248(2), pages 415-427.
    13. Maren Martens & Martin Skutella, 2009. "Flows with unit path capacities and related packing and covering problems," Journal of Combinatorial Optimization, Springer, vol. 18(3), pages 272-293, October.
    14. Forget, Nicolas & Gadegaard, Sune Lauth & Nielsen, Lars Relund, 2022. "Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs," European Journal of Operational Research, Elsevier, vol. 302(3), pages 909-924.
    15. Belhoul, Lyes, 2014. "Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée," Economics Thesis from University Paris Dauphine, Paris Dauphine University, number 123456789/14672 edited by Vanderpooten, Daniel.
    16. Markus Leitner & Ivana Ljubić & Markus Sinnl, 2015. "A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 118-134, February.
    17. Sedeño-Noda, Antonio & González-Martín, Carlos, 2010. "On the K shortest path trees problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 628-635, May.
    18. Sebastio, Stefano & Trivedi, Kishor S. & Wang, Dazhi & Yin, Xiaoyan, 2014. "Fast computation of bounds for two-terminal network reliability," European Journal of Operational Research, Elsevier, vol. 238(3), pages 810-823.
    19. Pedro Correia & Luís Paquete & José Rui Figueira, 2021. "Finding multi-objective supported efficient spanning trees," Computational Optimization and Applications, Springer, vol. 78(2), pages 491-528, March.
    20. Sune Lauth Gadegaard & Lars Relund Nielsen & Matthias Ehrgott, 2019. "Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 790-804, 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:ejores:v:260:y:2017:i:3:p:886-903. 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.