Network design with probabilistic capacities
Abstract
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 2018Keywords
All Related Versions
Funding Information
- Office of the Assistant Secretary for Health (FA9550-10-1-0168)
This publication has 40 references indexed in Scilit:
- Supermodular covering knapsack polytopeDiscrete Optimization, 2015
- Convex relaxations of chance constrained optimization problemsOptimization Letters, 2013
- The submodular knapsack polytopeDiscrete Optimization, 2009
- Maximizing a class of submodular utility functionsMathematical Programming, 2009
- Polymatroids and mean-risk minimization in discrete optimizationOperations Research Letters, 2008
- Network design arc set with variable upper boundsNetworks, 2007
- Cover and Pack Inequalities for (Mixed) Integer ProgrammingAnnals of Operations Research, 2005
- On capacitated network design cut?set polyhedraMathematical Programming, 2002
- Valid inequalities for problems with additive variable upper boundsMathematical Programming, 2001
- Flow pack facets of the single node fixed-charge flow polytopeOperations Research Letters, 2001