On the strength of cut-based inequalities for capacitated network design polyhedra

Christian Raack (raackzib.de)
Arie M.C.A. Koster (arie.kosterwbs.ac.uk)
Roland Wessäly (wessaelyzib.de)

Abstract: In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).

Keywords: cutset polyhedra, flow-cutset inequalities, capacitated network design, integer programming

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Network Optimization

Citation: ZIB Report 07-08, Konrad-Zuse-Zentrum für Informationstechnik Takustr. 7, D-14195 Berlin, Germany

Download: [PDF]

Entry Submitted: 06/07/2007
Entry Accepted: 06/08/2007
Entry Last Modified: 07/10/2007

Modify/Update this entry