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

Authors

  • Francis J. Vasko Kutztown University, USA
  • Yun Lu Kutztown University, USA
  • Bryan McNally Kutztown University, USA

DOI:

https://doi.org/10.47852/bonviewJCCE208918205514

Keywords:

cable-trench problem, integer programming software, CPLEX®, radio astronomy application, minimum spanning tree, shortest path, sensitivity analysis

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  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.

 

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.

Metrics

Metrics Loading ...

Downloads

Published

2022-01-29

How to Cite

Vasko, F. J., Lu, Y., & McNally , B. . (2022). A Simple Methodology that Efficiently Generates All Optimal Spanning Trees for the Cable-Trench Problem. Journal of Computational and Cognitive Engineering, 1(1), 13–20. https://doi.org/10.47852/bonviewJCCE208918205514

Issue

Section

Research Articles