On generalized network design polyhedra
Corinne Feremans (corinne.feremanshit.no)
Abstract: 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.
Keywords: generalized minimum spanning tree problem, generalized traveling salesman problem, polyhedral combinatorics
Category 1: Integer Programming (0-1 Programming )
Category 2: Combinatorial Optimization (Polyhedra )
Category 3: Applications -- OR and Management Sciences (Telecommunications )
Citation: C. Feremans, M. Labbé, A.N. Letchford & J.J. Salazar (2011) On generalised network design polyhedra. Networks, 58(2), 125-136.
Entry Submitted: 12/16/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|