A Simple Methodology that Efficiently Generates All Optimal Spanning Trees for the Cable-Trench Problem

Abstract

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  v₁ ∈ 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 v₁ 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.

Received: 28 December 2021 | Revised: 22 January 2022 | Accepted: 28 January 2022

Conflicts of Interest

The authors declare that they have no conflicts of interest to this work.