12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Generalised network design polyhedra
View graph of relations

« Back

Generalised network design polyhedra

Research output: Contribution to journalJournal article

Published

Journal publication date09/2011
JournalNetworks
Journal number2
Volume58
Number of pages12
Pages125-136
Original languageEnglish

Abstract

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.