Detecting Embedded Networks in LP Using GUB Structures and Independent Set Algorithms

In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two different approaches; the first is based on the notion of Markowitz merit count and the second exploits independent sets in the corresponding graphs. Our computational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorithms.