Decomposition Algorithms for Optimal Manufacturing and Power Systems Infrastructure Planning

This thesis addresses two challenging problems in the area of optimal infrastructure planning: continuous centralized-distributed facility location-allocation, and power systems generation expansion planning. We focus on decompositionapproaches for solving these optimization problems in face of nonconvexities, discrete decisions, integration of planning and scheduling, and optimization under uncertainty.Part I addresses continuous facility location-allocation problems with maximum capacity, also known as Capacitated Multi-FacilityWeber Problem (CMWP).This class of problems optimizes the 2-dimensional continuous location and allocation of facilities based on their maximum capacity and the given coordinatesof the suppliers and customers. We propose an extended version of the classic CMWP with fixed costs, multiple types of facilities and two sets of fixed points(suppliers and consumers), and formulate it as a nonconvex Generalized Disjunctive Programming model. We propose a Bilevel Decomposition algorithm and, based on the bounding properties of the subproblems, we prove its -convergence. We benchmark our Bilevel Decomposition against commercial global optimization solvers and the results show that our method is more effective at finding global optimal solutions. We then address the design and planning of manufacturing networks considering the option of centralized and distributed facilities, which is formulated as a multi-period version of our previous CMWP. To handle this added complexity, we propose an accelerated version of the Bilevel Decomposition with additional steps to reduce the feasible space. We benchmark the performance of the Accelerated Bilevel Decomposition algorithm against the originalBilevel Decomposition and the commercial global solvers and show that the accelerated algorithm outperforms the other options. Additionally, we illustrate the applicability of the proposed model and solution framework with a case study for a biomass supply chain. Part II addresses generation expansion planning problems in power systems.We start by investigating the impact of including operational and temporal details in a Generation Expansion Planning framework. This preliminary analysis shows that time-slice approaches tend to overestimate solar capacity and underestimate wind and natural gas capacity if compared to chronological hourly approaches. It also reveals that the latter consistently leads to lower unmet demand, implyingthe need for sufficient temporal resolution and chronology. Therefore, motivated by these results, we propose a deterministic Mixed-Integer Linear Programming(MILP) formulation for long-term planning of electric power infrastructure by simultaneously considering annual investment decisions and hourly operational decisions. We adopt judicious approximations and aggregations to improve its tractability and, to overcome computational challenges, we propose a decomposition algorithm based on Nested Benders Decomposition for multi-period MILP problems. Our decomposition adapts previous nested Benders methods by handling integer and continuous state variables. We apply the proposed modeling framework to a case study in the Electric Reliability Council of Texas (ERCOT)region, and demonstrate large computational savings from our decomposition. We then extend the proposed deterministic model to Multistage Stochastic Mixed-integer Programming in order to handle uncertainties. To be able to solve such large-scale model, we decompose the problem using Stochastic Dual Dynamic Integer Programming (SDDiP), and take advantage of parallel processingto solve it more efficiently. The proposed framework is also applied to a case study in the ERCOT region, and we show that the parallelized SDDiP algorithm allows the solution of instances with quadrillions of variables and constraints.This thesis makes several contributions both in modeling and algorithms. It addresses challenging practical problems and showcases the benefits of problem specificand structure-specific decomposition approaches to solve complex discrete optimization problems.