R.Wessäly, On the strength of cut-based inequalities for capacitated network design polyhedra, Konrad-Zuse-Zentrum für Informationstechnik

In this article, we study capacitated network design prob-lems.Weunify and extend polyhedral results for directed, bidirected, and undirected link capacity models. Valid inequalities based on a network cut are known to be strong in several special cases. We show that regard-less of the link model, facets of the polyhedra associated with such a cut translate to facets of the original net-work design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investiga-tion of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequal-ities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Librar