Network Design with Probabilistic Capacities
Preprint
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.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Robust network design: Formulations, valid inequalities, and computationsNetworks, 2013
- Maximizing a class of submodular utility functionsMathematical Programming, 2009
- Network design arc set with variable upper boundsNetworks, 2007
- Connectivity–splitting models for survivable network designNetworks, 2003
- Strong inequalities for capacitated survivable network design problemsMathematical Programming, 2000
- Robust solutions of Linear Programming problems contaminated with uncertain dataMathematical Programming, 2000
- A polyhedral approach to multicommodity survivable network designNumerische Mathematik, 1994
- The convex hull of two core capacitated network design problemsMathematical Programming, 1993
- Shortest paths, single origin‐destination network design, and associated polyhedraNetworks, 1993
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976