A characterization of the uncapacitated network design polytope

The uncapacitated network design problem is considered. The authors show that the feasible polytope of the continuous relaxation of this 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 interst since it implies the possiblity of solving the uncapacitated network design problem by a pivoting scheme.