Exact reliability optimization for series‐parallel graphs using convex envelopes
From MaRDI portal
Abstract: Given its wide spectrum of applications, the classical problem of all-terminal network reliability evaluation remains a highly relevant problem in network design. The associated optimization problem -- to find a network with the best possible reliability under multiple constraints -- presents an even more complex challenge, which has been addressed in the scientific literature but usually under strong assumptions over failures probabilities and/or the network topology. In this work, we propose a novel reliability optimization framework for network design with failures probabilities that are independent but not necessarily identical. We leverage the linear-time evaluation procedure for network reliability in the series-parallel graphs of Satyanarayana and Wood(1985) to formulate the reliability optimization problem as a mixed-integer nonlinear optimization problem. To solve this nonconvex problem, we use classical convex envelopes of bilinear functions, introduce custom cutting planes, and propose a new family of convex envelopes for expressions that appear in the evaluation of network reliability. Furthermore, we exploit the refinements produced by spatial branch-and-bound to locally strengthen our convex relaxations. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem.
Recommendations
- A global optimization problem in series-parallel networks with maximum reliability
- Topological optimization with a network reliability constraint
- Combinatorial optimization problems in the analysis and design of probabilistic networks
- A global optimization algorithm for reliable network design
- Publication:4862892
Cites work
- A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
- A survey of some network reliability analysis and synthesis results
- Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
- Classes of uniformly most reliable graphs for all-terminal reliability
- Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Computing the Reliability of Complex Networks
- Measuring and optimizing system reliability: a stochastic programming approach
- Network reliability and the factoring theorem
- On unreliability polynomials and graph connectivity in reliable network synthesis
- Reliable circuits using less reliable relays
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- Sixty years of network reliability
- Static network reliability estimation under the Marshall-Olkin copula
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The most reliable series-parallel networks
- The sample average approximation method for stochastic discrete optimization
- Topological optimization of reliable networks under dependent failures
This page was built for publication: Exact reliability optimization for series‐parallel graphs using convex envelopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6066247)
