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.

Convexification based on convex envelopes is ubiquitous in the non-linear optimization literature. Thanks to considerable efforts of the optimization community for decades, we are able to compute the convex envelopes of a considerable number of functions that appear in practice, and thus obtain tight and tractable approximations to challenging problems. We contribute to this line of work by considering a family of functions that, to the best of our knowledge, has not been considered before in the literature. We call this family *ray-concave* functions. We show sufficient conditions that allow us to easily compute closed-form expressions for the convex envelope of ray-concave functions over arbitrary polytopes. With these tools, we are able to provide new perspectives to previously known convex envelopes and derive a previously unknown convex envelope for a function that arises in probability contexts.

Natural hazards cause major power outages as a result of spatially-correlated failures of network components. However, these correlations between failures of individual elements are often ignored in probabilistic planning models for optimal network design. We use different types of planning models to demonstrate the impact of ignoring correlations between component failures and the value of flexible transmission assets when power systems are exposed to natural hazards. We consider a network that is hypothetically located in northern Chile, a region that is prone to earthquakes. Using a simulation model, we compute the probabilities of spatially-correlated outages of transmission and substations based on information about historical earthquakes in the area. We determine optimal network designs using a deterministic reliability criterion and probabilistic models that either consider or disregard correlations among component failures. Our results show that the probability of a simultaneous failure of two transmission elements exposed to an earthquake can be up to 15 times higher than the probability simultaneous failure of the same two elements when we only consider independent component failures. Disregarding correlations of component failures changes the optimal network design significantly and increases the expected levels of curtailed demand in scenarios with spatially-correlated failures. We also find that, in some cases, it becomes optimal to invest in HVDC instead of AC transmission lines because the former gives the system operator the flexibility to control power flows in meshed transmission networks. This feature is particularly valuable to systems exposed to natural hazards, where network topologies in post-contingency operating conditions might differ significantly from pre-contingency ones.

Dataset available at https://github.com/borelian/j.ejor.2017.09.023

Conf. Proc.

Proceedings of the 38th International Symposium on the Application of Computers and Operations Research in the Mineral Industry (APCOM 2017), Pages 13-27 to 13-33

Publication year: 2017

Articles

Transportation Research Part C: Emerging Technologies, 71: 86—107, 2016

Publication year: 2016

Conf. Proc.

Proceedings of LAGOS 2011 – VI Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes on Discrete Mathematics 37, 15-20.

Publication year: 2011