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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1002/net.22089 | NETWORKS |
Keywords | DocType | Volume |
convex envelopes, network reliability, nonlinear optimization, reliability optimization, series-parallel graphs | Journal | 80 |
Issue | ISSN | Citations |
2 | 0028-3045 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Javiera Barrera | 1 | 0 | 0.34 |
Eduardo Moreno | 2 | 0 | 0.34 |
Gonzalo Muñoz | 3 | 0 | 0.34 |
Pablo Romero | 4 | 0 | 0.34 |