Detecting embedded networks in LP using GUB structures and independent setalgorithms

In this paper, we present an alternative multi-stage generalized upper boun ds (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 t he second exploits independent sets in the corresponding graphs. Our comput ational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorith ms.