IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v4y2000i2d10.1023_a1009854922371.html
   My bibliography  Save this article

Combining Linear and Non-Linear Objectives in Spanning Tree Problems

Author

Listed:
  • Mauro Dell'Amico

    (Università di Modena e Reggio Emilia)

  • Francesco Maffioli

    (Politecnico di Milano)

Abstract

A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions. We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.

Suggested Citation

  • Mauro Dell'Amico & Francesco Maffioli, 2000. "Combining Linear and Non-Linear Objectives in Spanning Tree Problems," Journal of Combinatorial Optimization, Springer, vol. 4(2), pages 253-269, June.
    • Handle: RePEc:spr:jcomop:v:4:y:2000:i:2:d:10.1023_a:1009854922371
    DOI: 10.1023/A:1009854922371
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009854922371
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009854922371?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. Camerini, P. M. & Galbiati, G. & Maffioli, F., 1980. "Complexity of spanning tree problems: Part I," European Journal of Operational Research, Elsevier, vol. 5(5), pages 346-352, November.
    2. Matteo Fischetti & Gilbert Laporte & Silvano Martello, 1993. "The Delivery Man Problem and Cumulative Matroids," Operations Research, INFORMS, vol. 41(6), pages 1055-1064, December.
    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. Duin, C.W. & Volgenant, A., 2012. "On weighting two criteria with a parameter in combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 1-6.

    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. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    2. Silva, Marcos Melo & Subramanian, Anand & Vidal, Thibaut & Ochi, Luiz Satoru, 2012. "A simple and effective metaheuristic for the Minimum Latency Problem," European Journal of Operational Research, Elsevier, vol. 221(3), pages 513-520.
    3. Rivera, Juan Carlos & Murat Afsar, H. & Prins, Christian, 2016. "Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 249(1), pages 93-104.
    4. Zhang, Huili & Tong, Weitian & Lin, Guohui & Xu, Yinfeng, 2019. "Online minimum latency problem with edge uncertainty," European Journal of Operational Research, Elsevier, vol. 273(2), pages 418-429.
    5. Ribeiro, Glaydston Mattos & Laporte, Gilbert & Mauri, Geraldo Regis, 2012. "A comparison of three metaheuristics for the workover rig routing problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 28-36.
    6. Fausto Errico & Teodor Gabriel Crainic & Federico Malucelli & Maddalena Nonato, 2017. "A Benders Decomposition Approach for the Symmetric TSP with Generalized Latency Arising in the Design of Semiflexible Transit Systems," Transportation Science, INFORMS, vol. 51(2), pages 706-722, May.
    7. F. Angel-Bello & Y. Cardona-Valdés & A. Álvarez, 2019. "Mixed integer formulations for the multiple minimum latency problem," Operational Research, Springer, vol. 19(2), pages 369-398, June.
    8. Averbakh, Igor & Pereira, Jordi, 2015. "Network construction problems with due dates," European Journal of Operational Research, Elsevier, vol. 244(3), pages 715-729.
    9. Ricardo Fukasawa & Qie He & Yongjia Song, 2016. "A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem," Transportation Science, INFORMS, vol. 50(1), pages 23-34, February.
    10. Moshref-Javadi, Mohammad & Lee, Seokcheon & Winkenbach, Matthias, 2020. "Design and evaluation of a multi-trip delivery model with truck and drones," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    11. J. E. Beasley & M. Krishnamoorthy & Y. M. Sharaiha & D. Abramson, 2000. "Scheduling Aircraft Landings—The Static Case," Transportation Science, INFORMS, vol. 34(2), pages 180-197, May.
    12. Jan Mikula & Miroslav Kulich, 2022. "Solving the traveling delivery person problem with limited computational time," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(4), pages 1451-1481, December.
    13. Luiz Viana & Manoel Campêlo & Ignasi Sau & Ana Silva, 2021. "A unifying model for locally constrained spanning tree problems," Journal of Combinatorial Optimization, Springer, vol. 42(1), pages 125-150, July.
    14. Zhang, Zizhen & Qin, Hu & Zhu, Wenbin & Lim, Andrew, 2012. "The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach," European Journal of Operational Research, Elsevier, vol. 220(2), pages 295-304.
    15. Luo, Zhixing & Qin, Hu & Lim, Andrew, 2014. "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints," European Journal of Operational Research, Elsevier, vol. 234(1), pages 49-60.
    16. Bruni, M.E. & Khodaparasti, S. & Beraldi, P., 2020. "The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations," Omega, Elsevier, vol. 92(C).
    17. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    18. Sepehr Nemati & Oleg V. Shylo & Oleg A. Prokopyev & Andrew J. Schaefer, 2016. "The Surgical Patient Routing Problem: A Central Planner Approach," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 657-673, November.
    19. Igor Averbakh & Oded Berman, 1999. "A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems," Operations Research, INFORMS, vol. 47(1), pages 165-170, February.
    20. Ha-Bang Ban, 2021. "A metaheuristic for the delivery man problem with time windows," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 794-816, May.

    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:spr:jcomop:v:4:y:2000:i:2:d:10.1023_a:1009854922371. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.