Premium
The cut property under demand uncertainty
Author(s) -
Mattia Sara
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21621
Subject(s) - mathematical optimization , generalization , computer science , property (philosophy) , robust optimization , scope (computer science) , routing (electronic design automation) , cut , set (abstract data type) , graph , operations research , mathematics , theoretical computer science , artificial intelligence , computer network , mathematical analysis , philosophy , epistemology , segmentation , image segmentation , programming language
We consider the robust network design problem, which consists of choosing capacities for the edges of a graph so that a set of uncertain traffic demands can be routed. The scope of the paper is to study the robust cut property (RCP), that is, we investigate when the cut inequalities are sufficient to guarantee a feasible routing under demand uncertainty. We provide conditions that ensure the RCP. We discuss the generalization to the problem with uncertain demands of the results that are known for the problem without uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 159–168 2015