A characterization of the uncapacitated network design polytope (Q1200785)

The uncapaciated network design problem is a 0/1-problem well-known to be NP-hard. We show that, with the addition of some constraints barring solutions containing cyclic flows, the feasible polytope of the continuous relaxation of the uncapacitated network design problem has the property that any path along the edges of the convex hull of its integer points is also a path along the edges of the polytope itself. This property may be of computational interest since it implies the possibility of solving the problem by a pivoting scheme.