Optimization Online


On generalized network design polyhedra

Corinne Feremans (corinne.feremans***at***hit.no)
Martine Labbe (mlabbe***at***ulb.ac.be)
Adam Letchford (a.n.letchford***at***lancaster.ac.uk)
Juan-Jose Salazar-Gonzalez (jjsalaza***at***ull.es)

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
Entry Accepted: 12/16/2009
Entry Last Modified: 02/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society