Network design with probabilistic capacities
From MaRDI portal
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.
Recommendations
- THE PROBABILISTIC NETWORK DESIGN PROBLEM
- Single-commodity network design with random edge capacities
- Single commodity stochastic network design under probabilistic constraint with discrete random variables
- Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
- Capacitated network design with uncertain demand
Cited in
(21)- Physical network design to facilitate capacity reallocation
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Multi-service multi-facility network design under uncertainty
- Single-commodity network design with random edge capacities
- A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
- Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity
- Single commodity stochastic network design under probabilistic constraint with discrete random variables
- Internet protocol network design with uncertain demand
- Network reliability design via joint probabilistic constraints
- Probabilistic analysis of a network design problem heuristic
- A network recourse decomposition method for dynamic networks with random arc capacities
- Chance-constrained multi-terminal network design problems
- Algorithm to solve a chance-constrained network capacity design problem with stochastic demands and finite support
- Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information
- THE PROBABILISTIC NETWORK DESIGN PROBLEM
- Sum-Networks From Incidence Structures: Construction and Capacity Analysis
- Deterministic sampling algorithms for network design
- Using submodularity in solving the robust bandwidth packing problem with queuing delay guarantees
- Network reliability: Heading out on the highway
- Designing robust coverage networks to hedge against worst-case facility losses
- Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
This page was built for publication: Network design with probabilistic capacities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5228504)
