Large-Scale Optimization for Interdependent Infrastructure Systems

Abstract

The primary focus of this thesis is to develop decomposition methods for solving large-scale optimization problems, especially those arising in interconnected infrastructure systems. Several factors (e.g., the Internet-of-Things) are driving infrastructure systems to become more interdependent. As a result, these complex systems are increasingly exposed to a variety of risks and demand elaborate optimization modeling that allows risk-informed decision-making. The resulting optimization models, however, are often of large-scale and have computationally challenging properties. In this regard, this thesis studies how to formulate optimization models mitigating their risks and develop decomposition methods for solving these models with improved computational properties. We first present a network planning problem for electricity distribution grids and their associated communication networks. The problem is formulated as a two-stage mixed-integer linear program and is of large-scale, since it captures hundreds of potential disaster scenarios as well as grids’ dependencies on the communication systems. To deal with its vast size, we develop a branch-and-price algorithm that features a tight lower bound and various acceleration schemes that address degeneracy. The model and algorithm were evaluated on a variety of test cases, the results of which demonstrate the impact of the risk- aware planning decisions as well as the computational benefits of the proposed solution approach. Next, we propose a unit scheduling problem of electric grids. We introduce gas network awareness into the scheduling problem to alleviate risks from natural gas networks. The resulting optimization model is formulated as a bi-level optimization problem. To address inherent computational challenges in solving bilevel problems, we develop a dedicated Benders decomposition method for solving a certain class of bilevel problems (discrete-continuous bilevel problems), which subsumes the proposed model. The algorithm features a Benders subproblem decomposition technique that breaks down the Benders subproblem into two more tractable problems. We test the model and the solution approach on a practically-relevant network data set. The results demonstrate that the risk-aware opera- tional decision is instrumental in avoiding disruptions caused by gas system insecurity. It is also demonstrated that the proposed decomposition algorithm not only improves the computational performance of existing solution methods but also allows intuitive interpretation of Benders cuts.