Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Generalised network design polyhedra
AU - Feremans, Corinne
AU - Labbé, Martine
AU - Letchford, Adam N.
AU - Salazar-González, Juan-José
PY - 2011/9
Y1 - 2011/9
N2 - 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.
AB - 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.
KW - generalized minimum spanning tree problem
KW - generalized traveling salesman problem
KW - polyhedral combinatorics
U2 - 10.1002/net.20455
DO - 10.1002/net.20455
M3 - Journal article
VL - 58
SP - 125
EP - 136
JO - Networks
JF - Networks
SN - 0028-3045
IS - 2
ER -