Strong formulations for network design problems with connectivity requirements

The network design problem with connectivity requirements (NDC) includes as special cases a wide variety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and survivable network design problems. We develop strong formulations for two versions of the edge-connectivity NDC problem: unitary problems requiring connected network designs, and nonunitary problems permitting nonconnected networks as solutions. We (1) present a new directed formulation for the unitary NDC problem that is stronger than a natural undirected formulation; (2) project out two classes of valid inequalities—partition inequalities, and combinatorial design inequalities—that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem; and (3) show how to strengthen and direct nonunitary problems. Our results provide a unifying framework for strengthening formulations for NDC problems, and demonstrate the power of flow-based formulations for network design problems with connectivity requirements.