In recent years, there has been an increased literature on so-called Generalized Network Design Problems, such as the Generalized Minimum Spanning Tree Problem and the Generalized Traveling Salesman Problem. In such problems, the node set of a graph is partitioned into clusters, and the feasible solutions must contain one node from each cluster. Up to now, the polyhedra associated with these problems have been studied independently. We show that, by studying what we call generalized subgraph polyhedra, one can unify and generalise many of the known results in the literature. Along the way, we point out some interesting connections to other polyhedra, such as the quadratic semi-assignment polytope and the boolean quadric polytope.
Citation
C. Feremans, M. Labbé, A.N. Letchford & J.J. Salazar (2011) On generalised network design polyhedra. Networks, 58(2), 125-136.