IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v49y2025i4d10.1007_s10878-025-01289-0.html
   My bibliography  Save this article

A multi-objective perspective on the cable-trench problem

Author

Listed:
  • Lara Löhken

    (University of Wuppertal)

  • Michael Stiglmayr

    (University of Wuppertal)

Abstract

The cable-trench problem is defined as a linear combination of the shortest path and the minimum spanning tree problem. In particular, the goal is to find a spanning tree that simultaneously minimizes its total length and the total path length from a pre-defined root to all other vertices. Both, the minimum spanning tree and the shortest path problem are known to be efficiently solvable. However, a linear combination of these two objectives results in a highly complex problem. In this article, we introduce the bi-objective cable-trench problem which separates the two cost functions. We show that in general, the bi-objective formulation has additional compromise solutions compared to the cable-trench problem in its original formulation. To determine the set of non-dominated points and efficient solutions, we use $$\varepsilon $$ ε -constraint scalarizations in combination with a problem-specific cutting plane. Moreover, we present numerical results on different types of graphs analyzing the impact of density and cost structure on the cardinality of the non-dominated set and the solution time.

Suggested Citation

  • Lara Löhken & Michael Stiglmayr, 2025. "A multi-objective perspective on the cable-trench problem," Journal of Combinatorial Optimization, Springer, vol. 49(4), pages 1-29, May.
    • Handle: RePEc:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01289-0
    DOI: 10.1007/s10878-025-01289-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01289-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-025-01289-0?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. Y. P. Aneja & K. P. K. Nair, 1979. "Bicriteria Transportation Problem," Management Science, INFORMS, vol. 25(1), pages 73-78, January.
    2. Julius Bauß & Michael Stiglmayr, 2024. "Augmenting bi-objective branch and bound by scalarization-based information," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 85-121, August.
    3. D. Klingman & A. Napier & J. Stutz, 1974. "NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, INFORMS, vol. 20(5), pages 814-821, January.
    4. 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.
    5. Eric Landquist & Francis J. Vasko & Gregory Kresge & Adam Tal & Yifeng Jiang & Xenophon Papademetris, 2018. "The Generalized Steiner Cable-Trench Problem with Application to Error Correction in Vascular Image Analysis," Operations Research Proceedings, in: Andreas Fink & Armin Fügenschuh & Martin Josef Geiger (ed.), Operations Research Proceedings 2016, pages 391-397, Springer.
    Full references (including those not matched with items on IDEAS)

    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. Fritz Bökler & Sophie N. Parragh & Markus Sinnl & Fabien Tricoire, 2024. "An outer approximation algorithm for generating the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 263-290, August.
    2. Julius Bauß & Michael Stiglmayr, 2024. "Augmenting bi-objective branch and bound by scalarization-based information," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 85-121, August.
    3. Sedeno-Noda, A. & Gonzalez-Martin, C. & Gutierrez, J., 2005. "The biobjective undirected two-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 164(1), pages 89-103, July.
    4. Sedeno-Noda, A. & Gonzalez-Martin, C., 2000. "The biobjective minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 124(3), pages 591-600, August.
    5. Moradi, Siamak & Raith, Andrea & Ehrgott, Matthias, 2015. "A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 369-378.
    6. Hamacher, Horst W. & Pedersen, Christian Roed & Ruzika, Stefan, 2007. "Multiple objective minimum cost flow problems: A review," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1404-1422, February.
    7. Minghe Sun, 2005. "Warm-Start Routines for Solving Augmented Weighted Tchebycheff Network Programs in Multiple-Objective Network Programming," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 422-437, November.
    8. S. Dutta & S. Acharya & Rajashree Mishra, 2016. "Genetic algorithm based fuzzy stochastic transportation programming problem with continuous random variables," OPSEARCH, Springer;Operational Research Society of India, vol. 53(4), pages 835-872, December.
    9. Yang, X. Q. & Goh, C. J., 1997. "A method for convex curve approximation," European Journal of Operational Research, Elsevier, vol. 97(1), pages 205-212, February.
    10. Singh, Preetvanti & Saxena, P. K., 2003. "The multiple objective time transportation problem with additional restrictions," European Journal of Operational Research, Elsevier, vol. 146(3), pages 460-476, May.
    11. Pankaj Gupta & Mukesh Mehlawat, 2007. "An algorithm for a fuzzy transportation problem to select a new type of coal for a steel manufacturing unit," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 114-137, July.
    12. Festa, P. & Guerriero, F. & Laganà, D. & Musmanno, R., 2013. "Solving the shortest path tour problem," European Journal of Operational Research, Elsevier, vol. 230(3), pages 464-474.
    13. R. Fourer & H. Gassmann & J. Ma & R. Martin, 2009. "An XML-based schema for stochastic programs," Annals of Operations Research, Springer, vol. 166(1), pages 313-337, February.
    14. Mongeau, Marcel & Sartenaer, Annick, 1995. "Automatic decrease of the penalty parameter in exact penalty function methods," European Journal of Operational Research, Elsevier, vol. 83(3), pages 686-699, June.
    15. Moreno, Alfredo & Munari, Pedro & Alem, Douglas, 2019. "A branch-and-Benders-cut algorithm for the Crew Scheduling and Routing Problem in road restoration," European Journal of Operational Research, Elsevier, vol. 275(1), pages 16-34.
    16. Andrzej Jaszkiewicz & Thibaut Lust, 2017. "Proper balance between search towards and along Pareto front: biobjective TSP case study," Annals of Operations Research, Springer, vol. 254(1), pages 111-130, July.
    17. P. Beraldi & F. Guerriero & R. Musmanno, 1997. "Efficient Parallel Algorithms for the Minimum Cost Flow Problem," Journal of Optimization Theory and Applications, Springer, vol. 95(3), pages 501-530, December.
    18. Dayal Madhukar & Verma, Sanjay, 2015. "Multi-processor Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2015-03-25, Indian Institute of Management Ahmedabad, Research and Publication Department.
    19. Shaoxiang Zheng & Naiming Xie & Qiao Wu, 2025. "An exact approach for bi-objective non-identical batch processing machines scheduling," Annals of Operations Research, Springer, vol. 346(3), pages 2307-2347, March.
    20. Ahuja, Ravindra K., 1956- & Orlin, James B., 1953-, 1992. "Use of representative operation counts in computational testings of algorithms," Working papers 3459-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.

    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:49:y:2025:i:4:d:10.1007_s10878-025-01289-0. 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.