Capacitated network design using general flow-cutset inequalities

Christian Raack (raackzib.de)
Arie M.C.A. Koster (kosterzib.de)
Sebastian Orlowski (orlowskizib.de)
Roland Wessäly (wessaelyzib.de)

Abstract: This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities.

Keywords: Capacitated network design, mixed integer rounding, flow-cutset inequalities, SNDlib

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming (Cutting Plane Approaches )

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

Citation: ZIB Report 07-14, extended paper, first version in the proceedings of the International Network Optimization Conference (INOC 2007), Spa, Belgium, April 2007.

Download: [PDF]

Entry Submitted: 11/16/2006
Entry Accepted: 11/16/2006
Entry Last Modified: 07/10/2007

Modify/Update this entry