Vortrag von Lara Löhken

am 08.04.25 
um 15:30 
in 31-302 

wird Lara Löhken einen Vortrag über A Multi-objective Perspective on the Cable-Trench Problem halten. Interessierte Gäste sind herzlich willkommen.

Abstract:
The cable-trench problem is defined as a linear combination of the shortest path and the minimum spanning tree problem. The goal is to find a spanning tree that simultaneously minimizes its total length and the total path length from a pre-defined starting vertex to all other vertices. Both, the minimum spanning tree and the shortest path problem are known to be  efficiently solvable. However, a combination of these two objectives results in a highly complex problem. 

While the cable-trench problem is originally defined as a single-objective problem, namely a parameterized sum of minimum spanning tree and shortest path objective, we introduce the bi-objective cable-trench problem which separates the two cost functions. Indeed, by solving the bi-objective cable-trench problem, we can determine the entire solution set of the cable-trench problem. However, the bi-objective approach yields additional compromise solutions that cannot be found by solving the cable-trench problem in its originally formulation in general. To determine the set of non-dominated points and efficient solutions, we use epsilon-constraint scalarizations in combination with a problem-specific cutting plane. 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. Finally, we examine whether the solution set of the cable trench problem is a good representation (w.r.t. different representation indicators) of the non-dominated set of its bi-objective problem formulation.