Universität zu Köln

Cacchiani, Valentina, Juenger, Michael, Liers, Frauke, Lodi, Andrea and Schmidt, Daniel R. ORCID: 0000-0001-7381-912X (2016). Single-commodity robust network design with finite and Hose demand sets. Math. Program., 157 (1). S. 297 - 343. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

Abstract

We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as -Chvatal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Cacchiani, Valentina UNSPECIFIED UNSPECIFIED UNSPECIFIED Juenger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Lodi, Andrea UNSPECIFIED UNSPECIFIED UNSPECIFIED Schmidt, Daniel R. UNSPECIFIED orcid.org/0000-0001-7381-912X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-277103
DOI:	10.1007/s10107-016-0991-9
Journal or Publication Title:	Math. Program.
Volume:	157
Number:	1
Page Range:	S. 297 - 343
Date:	2016
Publisher:	SPRINGER HEIDELBERG
Place of Publication:	HEIDELBERG
ISSN:	1436-4646
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language COST Multiple languages Computer Science, Software Engineering; Operations Research & Management Science; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/27710