Strong Formulations for Network Design Problems with Connectivity Requirements

Abstract

The network design problem with connectivity requirements (NDC)models a wide variety of celebrated combinatorial optimizationproblems including the minimum spanning tree, Steiner tree, andsurvivable network design problems. We develop strong formulationsfor two versions of the edge-connectivity NDC problem: unitaryproblems requiring connected network designs, and nonunitaryproblems permitting non-connected networks as solutions. We(i) present a new directed formulation for the unitary NDC problemthat is stronger than a natural undirected formulation,(ii) project out several classes of valid inequalities---partitioninequalities, odd-hole inequalities, and combinatorial designinequalities---that generalize known classes of valid inequalitiesfor the Steiner tree problem to the unitary NDC problem, and(iii) show how to strengthen and direct nonunitary problems.Our results provide a unifying framework forstrengthening formulations for NDC problems, and demonstratethe strength and power of flow-based formulations fornetwork design problems with connectivity requirements.