Premium
Generalized network design polyhedra
Author(s) -
Feremans Corinne,
Labbé Martine,
Letchford Adam N.,
SalazarGonzález JuanJosé
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20455
Subject(s) - polyhedron , polytope , combinatorics , node (physics) , mathematics , quadric , quadratic equation , set (abstract data type) , computer science , discrete mathematics , geometry , structural engineering , engineering , programming language
In recent years, there has been an increased literature on so‐called generalized network design problems (GNDPs), such as the generalized minimum spanning tree problem and the generalized traveling salesman problem. In a GNDP, 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 different GNDPs have been studied independently. The purpose of this article is to show that it is possible, to a certain extent, to derive polyhedral results for all GNDPs simultaneously. Along the way, we point out some interesting connections to other polyhedra, such as the quadratic semiassignment polytope and the boolean quadric polytope. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011