A Simple Methodology that Efficiently Generates All Optimal Spanning Trees for the Cable-Trench Problem
Keywords:cable-trench problem, integer programming software, CPLEX®, radio astronomy application, minimum spanning tree, shortest path, networks, graph theory, sensitivity analysis
The Cable-Trench Problem (CTP) is defined as a combination of the Shortest Path and Minimum Spanning Tree Problems. Specifically, let G = (V , E) be a connected weighted graph with specified vertex v1 ∈ V (referred to as the root), length l(e) ≥ 0 for each e ∈ E, and positive parameters τ and γ. The Cable-Trench Problem is the problem of finding, for given values of τ and γ, a spanning tree T of G such that τlτ(T) + γlγ(T) is minimized, where lτ(T) is the total length of the spanning tree T and lγ(T) is the total path length in T from v1 to all other vertices of V. Consider the ratio R = τ/γ. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. This is the first article to present a methodology that iteratively uses integer programming software (CPLEX in this article) to efficiently generate all optimal spanning trees (GEAOST) for a CTP (for all values of R). An example will illustrate how sensitive the spanning trees solution can be to small changes in edge lengths. Also, GEAOST will be used to generate all optimal spanning trees for graphs based on a real-world radio astronomy application. How the sequence of all optimal spanning trees can be used for sensitivity analysis will be demonstrated.
How to Cite
Copyright (c) 2022 Authors
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.