Premium
Network design with probabilistic capacities
Author(s) -
Atamtürk Alper,
Bhardwaj Avinash
Publication year - 2018
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.21769
Subject(s) - probabilistic logic , polytope , mathematical optimization , knapsack problem , constraint (computer aided design) , computer science , exploit , function (biology) , set (abstract data type) , network planning and design , mathematics , combinatorics , artificial intelligence , computer network , evolutionary biology , biology , programming language , geometry , computer security
We consider a network design problem with random arc capacities and give a formulation with a probabilistic capacity constraint on each cut of the network. To handle the exponentially‐many probabilistic constraints a separation procedure that solves a nonlinear minimum cut problem is introduced. For the case with independent arc capacities, we exploit the supermodularity of the set function defining the constraints and generate cutting planes based on the supermodular covering knapsack polytope. For the general correlated case, we give a reformulation of the constraints that allows to uncover and utilize the submodularity of a related function. The computational results indicate that exploiting the underlying submodularity and supermodularity arising with the probabilistic constraints provides significant advantages over the classical approaches. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 16–30 2018