k-Partition-based facets of the network design problem

This article addresses the problem of designing a multi-commodity network using facilities of a fixed capacity to satisfy a given set of traffic demands. This problem (called the NDP) arises primarily in the design of high-capacity telecommunication networks. The k-partition of the NDP graph is introduced which results in a smaller k-node NDP. The main result of the article is a theorem, which shows that a facet inequality of the k-node problem translates into a facet of the original problem under a fairly mild condition, that is, the subgraph of each component of the k-partition be connected. This theorem is utilized to show that 2- and 3-partition-based inequalities identified by previous researchers yield families of facets for the original NDP. The structure of the 4-node NDP is explored to derive three different classes of valid inequalities and the conditions under which they are facet defining. The effectiveness of these inequalities is indicated by the computational experience on a 10-node example. (c) 2006 Wiley Periodicals, Inc.