Polyhedral Structure of the 4-Node Network Design Problem

This article studies the polyhedral structure of the 4-node network design problem (NDP). Using a theorem from the previous work of this author, the facets of the 4-node NDP can be translated into facets of larger size problems. The knowledge of complete polyhedral description of the 4-node NDP is important because it implies complete knowledge of 4-partition-based facets of larger NDPs. After reviewing the previously known facets of the 4-node NDP, a new class of facets is derived. An enumerative methodology is presented for determining whether a given set of inequalities provides a complete polyhedral description. By implementing this methodology in a computer code, it is determined that the known facets of the 4-node NDP indeed provide a complete polyhedral description of the problem. Working of the proof methodology is illustrated with examples, and the results of the computer enumeration are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(3),139-149 2009