A Deep Generative Learning Approach for Two-stage Adaptive Robust Optimization
Aron Brenner Rahman Khorramfar Jennifer Sun Saurabh Amin





1,3]Aron BrennerCorresponding author. Email: abrenner@mit.edu
1,2]Rahman Khorramfar
4]Jennifer Sun
1,2,3]Saurabh Amin
[1]Laboratory for Information & Decision Systems, Massachusetts Institute of Technology, Cambridge, MA
[2]MIT Energy Initiative, Massachusetts Institute of Technology, Cambridge, MA
[3]Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MA
[4]Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA

A Deep Generative Learning Approach for Two-stage Adaptive Robust Optimization
    [
    
==============================================================================

§ ABSTRACT 
Two-stage adaptive robust optimization is a powerful approach for planning under uncertainty that aims to balance costs of “here-and-now” first-stage decisions with those of “wait-and-see” recourse decisions made after uncertainty is realized. To embed robustness against uncertainty, modelers typically assume a simple polyhedral or ellipsoidal set over which contingencies may be realized. However, these simple uncertainty sets tend to yield highly conservative decision-making when uncertainties are high-dimensional. In this work, we introduce AGRO, a column-and-constraint generation algorithm that performs adversarial generation for two-stage adaptive robust optimization using a variational autoencoder. AGRO identifies realistic and cost-maximizing contingencies by optimizing over spherical uncertainty sets in a latent space using a projected gradient ascent approach that differentiates the optimal recourse cost with respect to the latent variable. To demonstrate the cost- and time-efficiency of our approach experimentally, we apply AGRO to an adaptive robust capacity expansion problem for a regional power system and show that AGRO is able to reduce costs by up to 7.8% and runtimes by up to 77% in comparison to the conventional column-and-constraint generation algorithm. 








empty



=0pt



§ INTRODUCTION

Growing interest in data-driven stochastic optimization has been facilitated by the increasing availability of more granular data for a wide range of settings where decision-makers hedge against uncertainty and shape operational risks through effective planning. Adaptive robust optimization (ARO) – also referred to as adjustable or two-stage/multi-stage robust optimization <cit.> – is one class of models that has found applications in optimization of industrial processes <cit.>, transportation systems <cit.>, and energy systems planning <cit.>. In this work, we aim to solve data-driven two-stage ARO problems with high-dimensional uncertainty that take the form

    min_x∈𝒳 { c^⊤ x   +  λmax_ξ∈𝒰min_y∈𝒴(ξ, x) d^⊤ y  }.

Here, x represents “here-and-now” first-stage decisions while y represents “wait-and-see” recourse decisions made after the random variable ξ∈ℝ^D is realized. 
The set 𝒰⊂ℝ^D represents the uncertainty set, encompassing all possible realizations of ξ that must be accounted for when identifying the optimal first-stage decisions x. In this work, we assume first-stage decisions x belongs to a mixed-integer feasible set 𝒳 while recourse decisions y belong to a polyhedral set 𝒴(ξ, x) = {y | By ≥ b(ξ) - A(ξ)x,  y≥ 0} , where b(ξ) and A(ξ) are affine functions. Additionally, we adopt a complete recourse assumption, i.e., 𝒴(ξ, x) ≠∅ for any ξ∈𝒰, x∈𝒳.

As an illustrative example, consider the problem of capacity expansion planning for a supply chain network. In this case, x denotes discrete long-term decisions (i.e., constructing warehouses), which require an upfront investment c^⊤ x. As the day unfolds and demands ξ are known, production and transportation decisions y∈𝒴(ξ,x) can be made to meet demand at a recourse cost of d^⊤ y. To ensure robustness against uncertain demand, first-stage decisions balance investment costs with the λ-weighted worst-case daily production and transportation cost incurred over the uncertainty set 𝒰.

The uncertainty set 𝒰 plays a large role in shaping planning outcomes and as such must take into account the available data as well as the planner's risk preferences. To optimize risk measures such as worst-case costs or value-at-risk more precisely, it is advantageous to construct 𝒰 based on the desired risk tolerance and obtain probabilistic guarantees on the recourse cost before optimizing. In the case of nonadaptive robust optimization (RO), various probabilistic guarantees can be obtained for a range of conventional (e.g., ellipsoidal, budget) uncertainty sets depending on in the information one has about the distribution of uncertainty p_ξ <cit.>. These results, which give guarantees for certain classes of constraints admitting a closed-form expression, are not easily extended to the case of recourse costs in ARO problems. While an approximate α-probability guarantee can be obtained using an uncertainty set that contains α-fraction of ξ observations, such an approach can yield increasingly conservative solutions to (<ref>) – i.e., solutions that “over-invest” in anticipation of extreme contingencies – in settings with high-dimensional uncertainty as the size of such uncertainty sets scale exponentially with D <cit.>.

In this work, we propose AGRO, a solution algorithm that embeds a variational autoencoder within a column-and-constraint generation (CCG) scheme to perform adversarial generation of realistic contingencies for adaptive robust optimization. We list our contributions below:


    
  * Extension of deep data-driven uncertainty sets to ARO. We extend recent approaches for learning tighter uncertainty sets in RO <cit.> to the case of ARO, a richer class of optimization models that allows for recourse decisions to be made after uncertainty is realized.

    
  * ML-assisted optimization using exact solutions. Rather than approximate decision-making with a predictive model <cit.>, we train a generative model to approximate the distribution of uncertain parameters. Consequently, AGRO does not require building a large dataset of solved problem instances for training a predictive model and optimizes with respect to exact recourse costs rather than an ML-based approximation.

    
  * Application to planning with observed energy supply/demand data. We apply our solution algorithm to the problem of long-term power system planning under hourly supply/demand uncertainties – a data-driven setting with high-dimensional and nonlinearly correlated uncertainty – and show reductions in both costs and runtimes when compared to a conventional CCG algorithm.


The remainder of the text is organized as follows. In Sec. <ref>, we describe the state of the art for modeling with ARO. First, we describe the CCG solution framework and outline standard approaches for uncertainty set construction, which together provide a basis for discussion of recent developments integrating learning and optimization for RO/ARO. In Sec. <ref>, we describe our solution algorithm in full, which integrates an uncertainty set representation learned by a variational autoencoder (VAE) within the CCG algorithm. Finally, in Sec. <ref>, we apply our CCG algorithm to the case of capacity expansion planning for a regional power system and compare against the conventional CCG approach.



§ PRELIMINARIES



 §.§ Uncertainty Sets

A fundamental modeling decision in both robust optimization and ARO is the definition of the uncertainty set 𝒰, representing the range of uncertainty realizations for which the first stage decision x must be robust. The most widely adopted uncertainty sets are variations of the box, budget, and ellipsoidal uncertainty sets <cit.>, which can be obtained in a data-driven setting as


    𝒰^box   = {ξ∈ℝ^D  | ξ̂^min≤ξ_i ≤ξ̂^max,  ∀ i=1,…,D }
    𝒰^budget   = {ξ∈ℝ^D  | ∑_i=1^D Σ̂_ii^-1|ξ_i - μ̂_i| ≤Γ_budget}
    𝒰^ellipse   = {ξ∈ℝ^D  | (ξ - μ̂)^⊤Σ̂^-1(ξ - μ̂) ≤Γ_ellipse}.


Here, μ̂, Σ̂, ξ̂^min, and ξ̂^max denote the empirical mean, covariance, minimum value, and maximum value of the empirical distribution of ξ while the Γ parameters denote the uncertainty “budgets.” To obtain an approximate α-probability guarantee of feasibility, one can select Γ such that 𝒰 covers an α-fraction of observed ξ realizations. Alternatively, one can take a distributionally robust 
approach to selecting Γ by leveraging concentration inequalities.



 §.§ Column-and-Constraint Generation

Once 𝒰 is defined, one can apply a number of methods to either exactly <cit.> or approximately <cit.> solve the ARO problem. Here, we focus our discussion on the CCG algorithm <cit.> due to its prevalence in the ARO literature (including its use in recent learning-assisted methods <cit.>) and because it provides a nice foundation for introducing AGRO in Sec. <ref>. The CCG algorithm is an exact solution method for ARO that iteratively identifies “worst-case” uncertainty realizations ξ^i by maximizing recourse costs for a given first-stage decision x^*. These uncertainty realizations are added in each iteration to the finite scenario set 𝒮, which is used to instantiate the main problem

    min_x,y,γ      c^⊤ x + λγ
    s.t.      x ∈𝒳
        A(ξ^i) x + B y^i ≥ b(ξ^i)    ξ^i∈𝒮
        y^i ≥ 0     i = 1,…,|𝒮| 
       γ≥ d^⊤ y^i     i = 1,…,|𝒮|

where γ denotes the worst-case recourse cost over 𝒮 (see (<ref>)). In each iteration i of the CCG algorithm, additional variables (i.e., columns) y^i and constraints y^i ∈𝒴(ξ^i, x) corresponding to the most recently identified worst-case realization are added to the main problem.

Solving the main problem yields a set of first-stage decisions, x^*, which are fixed as parameters in the adversarial subproblem

    max_ξ∈𝒰min_y ≥ 0 {d^⊤ y  |  B y ≥ b(ξ) - A(ξ) x^* }.

Solving the adversarial subproblem yields a new worst-case realization ξ^i to be added to 𝒮. Such a max-min problem can be solved by constructing the dual of the inner minimization problem and maximizing d^⊤ y subject to Karush–Kuhn–Tucker (KKT) conditions of the inner minimization problem <cit.>. Despite its prominence in the literature, the KKT reformulation of (<ref>) yields a potentially large bilinear problem; specifically, one for which the number of bilinear terms scales linearly with D. This need to repeatedly solve a large-scale bilinear program can cause CCG to be computationally unwieldy in the case of high-dimensional uncertainty. To this end, a number of alternative solution approaches – including some that leverage ML methods – have been proposed that approximate recourse decisions in order to yield more tractable reformulations, which we discuss next.



 §.§ Learning for Adaptive and Single-stage RO

As an alternative to CCG and other exact methods, linear decision rules (LDRs) are commonly used to approximate recourse decisions as affine functions of uncertainty <cit.>. To better approximate recourse costs using a richer class of functions, <cit.> propose a “deep lifting” procedure with neural networks to learn piecewise LDRs.  <cit.> train decision trees to predict near-optimal first-stage decisions, worst-case uncertainty, and recourse decisions, which are deployed as part of a solution algorithm for ARO. Similarly, <cit.> train a neural network to approximate optimal recourse costs conditioned on first-stage decisions, which they embed within a CCG-like algorithm.

While these learning-assisted methods address some shortcomings of conventional methods (such as CCG) in reducing runtimes, several challenges remain. The first of these is looseness of uncertainty representation. These methods, along with the conventional CCG algorithm, fail to address the challenge of “loose” uncertainty sets which arises in the case of high-dimensional uncertainty. While uncertainty sets of the form (<ref>) may be effective in approximating high-density regions in low-dimensional settings, they are prone to yielding costly, overly conservative solutions when ξ is high-dimensional <cit.>. The second such challenge is inexactness; specifically, these methods optimize first-stage decisions with regard to a learned approximation of the recourse cost rather than the actual recourse cost, min_y∈𝒴(ξ,x) d^⊤ y. Accordingly, the quality of the approximation depends on the extensiveness of pre-training and amount of training data matching (ξ, x) pairs to corresponding recourse costs. Obtaining such training data in particular can be computationally onerous as it involves solving a large number of linear programs.

In the case of nonadaptive RO, some recent works have addressed the issue of looseness by learning “deep data-driven” uncertainty sets. <cit.> propose using clustering and dimensionality reduction methods to construct data-driven uncertainty sets as unions or intersections of ellipsoids and polyhedra. More similarly to our work, <cit.> introduce a solution algorithm that first constructs a tight uncertainty set as the image of a Gaussian superlevel set under a neural network-learned transformation and then iteratively identifies worst-case realizations by optimizing “through” the neural network. <cit.> extend their approach to construct uncertainty sets conditioned on the observation of a subset of covariates. In these two studies, the adversarial subproblem corresponds to a tractable mixed-binary linear program with as many binary variables as hidden units in the neural network. While <cit.> and <cit.> show their deep data-driven uncertainty set approach reduces costs in the case of nonadaptive RO, these approaches cannot be easily extended to ARO. This is because the resulting subproblem will correspond to a max-min problem, which does not admit a tractable duality-based reformulation due to the presence of binary variables.



§ AGRO

In this work, we propose AGRO, a solution algorithm that performs adversarial generation for robust optimization. As described in Fig. <ref>, AGRO modifies the conventional CCG algorithm in two key ways: (1) To reduce looseness (and by consequence, costs) we construct an uncertainty set with (approximately) known probability mass by training a VAE and projecting spherical uncertainty sets from the latent space into the space of ξ. (2) Because the recourse cost does not admit a closed-form expression, the adversarial subproblem cannot be formulated as a mixed-integer program as was the case in <cit.>. Consequently, we solve the subproblem by differentiating the recourse cost with respect to ξ and performing gradient ascent to identify worst-case realizations.



Table <ref> compares AGRO to related works for ARO and single-stage RO. Our approach is similar to that of <cit.> in that we optimize “through” a trained neural network to obtain worst-case scenarios within a CCG algorithm. While <cit.> approximate recourse decisions using a predictive model to reduce runtime, however, we exactly solve the recourse problem as a linear program in each iteration while leveraging a trained VAE to approximate the distribution of uncertainty. Doing so also removes the computational effort required for building a dataset of recourse problem solutions – i.e., solving a large number of linear programs to obtain an accurate predictive model for recourse cost given ξ and x. Additionally, our approach extends the work of <cit.> and <cit.> in constructing tighter uncertainty sets using deep learning to the problem setting of ARO.





 §.§ Deep Data-Driven Uncertainty Sets

Toward addressing the challenge of looseness, we take a VAE approach to learning tight uncertainty sets as nonlinear and differentiable transformations of convex uncertainty sets lying in the latent space ℝ^L with L < D. We let z ∼ p_z = 𝒩(0,I_L) be an isotropic Gaussian random variable and let h_ϕ: ℝ^D →ℝ^L and g_θ: ℝ^L →ℝ^D respectively denote the encoder and decoder of a variational autoencoder (VAE) model trained to generate samples from p_ξ <cit.>. Specifically, h_ϕ is trained to map samples of uncertainty realizations to samples from the isotropic Gaussian distribution while g_θ is trained to perform the reverse mapping. Here, L denotes the VAE bottleneck dimension, which is a hyperparameter that significantly influences the diversity and quality of generated samples and is generally tuned through a process of trial and error. We note that our approach can be extended to other classes of deep generative models that learn such a mapping from 𝒩(0,I_L) to p_ξ such as generative adversarial networks <cit.>, normalizing flows <cit.>, and diffusion models <cit.>. However, we employ a VAE architecture as such models are known to exhibit relatively high stability in training and low computational effort for sampling <cit.>, making them highly conducive to integration within an optimization framework.

We let 𝒵 be the L-ball ℬ(0,r) with r chosen to be the minimum value such that an α-fraction of projected uncertainty realizations h_ϕ(ξ) are observed to fall within 𝒵. Since 𝒵 is closed and bounded, the image of 𝒵 under g_θ, which is continuous, will also be a closed and bounded (but not necessarily convex) set g_θ(𝒵) ∈ℝ^D. Unless g_θ is also invertible, the probability mass contained in this set under p_ξ will not necessarily equal α, the sample estimate of probability mass in 𝒵 under p_z <cit.>. Nevertheless, we observe that constraining z to 𝒵 (and by extension, ξ to g_θ(𝒵)) discourages generating uncertainty realizations that are unrealistic or lie outside of high-density regions of p_ξ. This is intuitive as realizations lying farther from the origin in the latent space are estimated to have lower likelihood under the VAE Gaussian prior <cit.>. Fig. <ref> shows a comparison of conventional uncertainty sets against a tighter uncertainty set constructed by the proposed VAE-based method for samples from the bivariate “moons” distribution <cit.>.





 §.§ Adversarial Subproblem

Given a decoder (i.e., generative model) g_θ: ℝ^L →ℝ^D, latent uncertainty set 𝒵 = ℬ(0, r), and first-stage decision x^*, we then formulate the adversarial subproblem as

    max_z∈𝒵 min_y {d^⊤ y  |  B y^i ≥ b(g_θ(z)) - A(g_θ(z)) x^* },

which substitutes g_θ(z) and 𝒵 for ξ and 𝒰 respectively in (<ref>). We denote the optimal objective value of the recourse problem as a function of ξ by f: ℝ^D→ℝ (see Fig. <ref>). It is then possible to differentiate f with respect to ξ by implicitly differentiating the optimality conditions of the recourse problem at an optimal solution <cit.>. Doing so provides an ascent direction for maximizing f with respect to ξ, and by applying the chain rule, z, which can be leveraged to maximize f using first-order optimization methods. By maximizing f using projected gradient ascent over 𝒵, we discourage selection of worst-case realizations that fall outside high-density regions of p_ξ.

Importantly, projected gradient ascent is not guaranteed to converge to a worst-case uncertainty realization as solving max_z f(g_θ(z), x^*) requires maximizing the composition of f, which is convex <cit.>, with g_θ, which is not necessarily convex nor concave. As such, the adversarial problem requires maximizing a nonconcave function, which does not yield convergence guarantees to global maxima. To encourage discovery of global maxima, we solve the adversarial subproblem multiple times in each iteration with I different, random initializations of z. Specifically, each initialization requires that we first randomly sample a latent variable z from a distribution p_s (e.g., the truncated normal or uniform distribution) supported on 𝒵. We then transform z to obtain the uncertainty realization ξ = g_θ(z) and solve the inner linear minimization problem with respect to ξ to obtain f(ξ, x^*) and ∂ f / ∂ξ. Using automatic differentiation, we obtain the gradient of ξ with respect to z and perform the update

    z ←Π_𝒵( z + η∂ f(ξ, x^*)/∂ξξ/ z),

where η > 0 denotes the step-size hyperparameter and Π_𝒵 denotes the projection operator given by

    Π_𝒵(z) = 
            z,     z ∈𝒵
    
            r ·z/z_2,     z ∉𝒵.

This procedure is repeated until a convergence criterion is met. At this point, the worst-case uncertainty realization obtained over all I initializations is added to 𝒮 and the main problem is re-optimized, which completes one iteration of the AGRO solution algorithm. AGRO terminates when the worst-case total costs estimated by the main problem and subproblem have converged, i.e., (c^⊤ x^* + λ f(ξ^i, x^*)) - (c^⊤ x^* + λγ)/c^⊤ x^* + λγ≤ϵ for some convergence tolerance ϵ. The full pseudocode for AGRO is now presented in Alg. <ref>.





§ APPLICATION TO CAPACITY EXPANSION PLANNING

Stochastic capacity expansion models have become a centerpiece for long-term planning of energy generation, transmission, and distribution infrastructure under supply, demand, and cost uncertainties <cit.>. A number of recent works have adopted ARO formulations for future energy systems planning with a particular focus on ensuring system reliability under mass adoption of renewable energy with intermittent and uncertain supply <cit.>. In capacity expansion settings with high spatiotemporal fidelities, supply and demand uncertainties are complex, high-dimensional, and nonunimodal, exhibiting nonlinear correlations such as temporal autocorrelations and spatial dependencies. These patterns cannot be accurately captured by conventional uncertainty sets such as those introduced in (<ref>). As a result, tightening uncertainty representations for robust capacity expansion planning has the potential to significantly lower investment costs over conventional ARO methods while still maintaining low operational costs day-to-day.

In this section, we apply AGRO to a two-stage adaptive robust generation and transmission expansion planning problem for the New England transmission system. We assume a data-driven setting with high-dimensional uncertainty corresponding to hourly demand as well as solar, onshore wind, and offshore wind capacity factors (average power output divided by the plant's maximum production capacity) at each node. Our results demonstrate AGRO's ability to reduce both costs and runtimes when compared to solutions obtained by the CCG algorithm. In what follows, we briefly describe the adaptive robust generation and transmission expansion problem and leave the complete formulation in Appendix. <ref>.



 §.§ Formulation

The generation and transmission expansion problem we present most closely follows that of <cit.> and has two stages: an initial investment stage and a subsequent economic dispatch (i.e., recourse) stage. The objective function is a weighted sum of investment costs plus annualized worst-case economic dispatch costs. Investment decisions are made at the node level and include installed capacities for (1)  dispatchable, solar, onshore wind, and offshore wind power plants at each node; (2) battery storage at each node; (3)  transmission lines. In the first stage, the capacity of new dispatchable and renewable power plants as well as new transmission lines are constrained by their respective upper bounds.  The economic dispatch stage occurs after the realization of uncertain demand and supply. This stage determines optimal hourly generation, power flow, and storage decisions to minimize the combined cost of load shedding and variable cost for dispatchable generation; these decisions are subject to ramping, storage, and flow balance constraints. To simulate inter-day dynamics of storage and ramping, we implement circular indexing, which links battery state-of-charge and dispatchable generation rates at the end of the day with those at the beginning <cit.>.



 §.§ Experimental Setup

In our experiments, we utilize hourly demand and capacity factor projections for a six-node zonal representation of New England, which yields an uncertain random variable ξ with 349 distinct features after data processing (see <ref>) <cit.>. We segment the dataset to perform a five-fold cross-validation with each fold having a held-out set of 1000 samples and report cross-validated estimates of total costs. Specifically, for a given fold, we train one VAE using an 80/20 training/validation split on the in-sample data, solve the ARO problem using Alg. <ref>, and obtain an out-of-sample cost estimate in each iteration by fixing x^* and computing c^⊤ x^* + λF̂^-1(α), where F̂^-1(α) is the out-of-sample α-quantile estimate of f(ξ, x^*).

As a baseline method, we report results for CCG using an uncertainty set constructed from the intersection of the budget and box uncertainty sets (see (<ref>)), which is commonly used in the power systems literature <cit.>. For our experiments, Γ is selected such that 𝒰 covers α=95% of the training set. For AGRO, we likewise select r such that the uncertainty set 𝒵 = ℬ(0, r) covers 95% of the training set after being projected by h_ϕ into the L-dimensional latent space. Additionally, we report results for a range of latent dimensionalities, L∈{2,4,8,16}. Additional details regarding the VAE architecture and training setup are given in Appendix <ref>



 §.§ Results

1.1



Cost and runtime. Results for AGRO and CCG costs and runtimes are shown in Table <ref>. Regarding planning costs, we observe that AGRO obtains investment decisions that yield lower costs than CCG as evaluated by out-of-sample estimates. In particular, costs are minimized by AGRO with L=2 (yielding a 7.8% reduction in costs over CCG) and appear to increase with L. AGRO with L=2 also obtains the lowest total runtime, which includes both VAE training and optimization, while CCG obtains the highest total runtime (approximately 4.4 times that of AGRO with L=2). We also find that the CCG subproblem is solved more quickly than the AGRO subproblem, whose runtime we observe to increase with L. We note that the AGRO subproblem includes multiple initializations of z, which causes its runtime to vary as more initializations are required in later iterations to obtain a new worst-case realization.

Approximation of value-at-risk. Besides sample-estimated costs, we also compare the accuracy of all methods in approximating value-at-risk (VaR), a risk measure that quantifies near worst-case costs, defined by min{β∈ℝ|ℙ_ξ (f(ξ, x) ≤β) > α}. First, we compare the final objective value, c^⊤ x^* + λγ with x^* and γ obtained from the final iteration of solving, against the sample-estimated cost. We observe that, for all methods, the final objective value is greater than the out-of-sample recourse cost estimate. We also report the mean absolute percent error of the main problem objective value, i.e., c^⊤ x^* + λγ, compared to the out-of-sample estimate across all iterations. For both quantities, we observe that AGRO is able to obtain a much tighter estimate of VaR than CCG, which yields an average error of 78.6% over the course of solving. The looseness of this approximation explains the high costs obtained by CCG. Specifically, the identification of improbable but cost-maximizing uncertainty realizations results in consistent over-estimation of VaR and subsequent over-investment as CCG aims to reduce costs for these improbable realizations. We dedicate the remainder of this subsection to more precisely understanding how AGRO improves over CCG in tightly approximating VaR and consequently reducing costs.

We first visualize the relative performance in approximating VaR for all methods in Fig. <ref>, which plots the estimated worst-case cost obtained from solving the subproblem f(ξ^i, x^*) against the out-of-sample estimate F̂^-1(α) for all iterations of solving in all five folds of cross-validation. We also show standard metrics of generative model fidelity (i.e., precision, density) and diversity (i.e., recall, coverage) for the VAE models in Table <ref>. Additional details regarding these metrics based on <cit.> are provided in Appendix <ref>. From Fig. <ref>, we first observe that f(ξ^i, x^*) and F̂^-1(α) are highly correlated, which suggests that maximizing the recourse cost serves as a useful proxy for estimating VaR. We also observe that in all cases except AGRO with L=2, f(ξ^i, x^*) is almost always greater than F̂^-1(α). This is intuitive as the uncertainty set is designed to contain an α-fraction of realizations, and consequently, the worst-case recourse cost obtained over this set will provide a “safe” approximation (i.e., over-estimate) of VaR at level α. This over-estimating effect is also reflected in the consistent gap between the final objective value and the out-of-sample cost estimate (see Table <ref>). This is not the case, however, with L=2 as the associated VAE models obtain a much lower coverage than those for L > 2 (see Table <ref>). As such, the uncertainty set does not sufficiently cover the high-density region of p_ξ, which leads to occasional under-estimation of VaR. AGRO with L=2 nevertheless obtains the lowest sample-estimated costs of all methods. Together, these results suggests that, while poor VAE fidelity or diversity can cause AGRO to fail to identify cost-maximizing realizations, the end result is not necessarily a consistent under-estimation of VaR. This is a consequence of the “safe” uncertainty set, which introduces a systemic over-estimating effect with regard to VaR and counteracts the systemic under-estimation resulting from diminished VAE diversity and fidelity. These results highlight the dependence of solution quality on VAE performance while also demonstrating that the ideal choice of L is not necessarily one that maximizes sample fidelity and diversity, and consequently, should be tuned with consideration of downstream optimization outcomes.





Visualizing worst-case uncertainty. Towards understanding how different uncertainty sets impact conservatism of first-stage decision-making, we compare samples of obtained worst-case realizations in Fig. <ref>. Specifically, we plot the solution to the adversarial subproblem for the final iteration of one fold of cross-validation for CCG and AGRO with L=2 and L=16. Fig. <ref> demonstrates the way in which worst-case realizations obtained by CCG using a budget uncertainty set are unrealistically adversarial. In particular, CCG generates an uncertainty realization in which solar and wind capacity factors drop sharply to zero before immediately rising to their nominal values. Additionally, weather-related correlations between variables are not maintained; most notably, the positive correlation between load and solar capacity factors as well as the spatial correlation of load across the system are not observed. Accounting for these supply and demand features during investment planning is essential for effectively leveraging the complementarities between generation, storage, and transmission. On the other hand, AGRO is able to identify uncertainty realizations that are simultaneously cost-maximizing and realistic. This can be observed from the way in which selected realizations demonstrate realistic temporal autocorrelation (i.e., smoothness) and show a less improbable combination of low solar capacity factors with moderate load.

Comparing the two AGRO-generated realizations, we observe that the L=16 case yields a more cost-maximizing realization than the L=2 case. In particular, loads are higher while capacity factors are lower. Additionally, the generated load and capacity factor time series in the L=2 case are smoother than those in the L=16 case, which can result in under-estimation of load shedding costs resulting from highly fluctuating loads and under-investment in dispatchable generation. These observations, which reflect the fidelity and density results shown in Table <ref>, explain the occasional under-estimation of recourse costs by AGRO with L=2 (see Fig. <ref>) as well as the lower overall costs resulting from reduced conservatism (see Tab. <ref>).





§ CONCLUSION

Increasing availability of data for operations of large-scale systems has inspired growing interest in data-driven optimization. In this work, we extend learning-based approaches for more precise uncertainty representation to the setting of ARO, a powerful framework for planning under uncertainty. We propose AGRO, a modification of the conventional column-and-constraint generation algorithm for chance-constrained ARO problems. AGRO takes a gradient ascent approach to maximizing the value of the inner minimization problem using differentiable convex optimization and adds worst-case uncertainty realizations to a master problem. By leveraging a VAE to project spherical uncertainty sets from a latent space to nonconvex uncertainty sets in a higher dimensional uncertainty space, AGRO identifies worst-case realizations that are not only adversarial but also more likely to occur than those identified from conventional uncertainty sets. Finally, we applied AGRO to the case of capacity expansion planning under supply/demand uncertainty to experimentally demonstrate AGRO's efficacy in greatly reducing both costs and runtimes for ARO.

plainnat




§ CAPACITY EXPANSION MODEL

The capacity expansion model is given by


    min_x     ∑_i∈𝒩 c^d x_i^d + ∑_i∈𝒩∑_p∈𝒫 c^p x_i^p + ∑_i∈𝒩 c^b x_i^b + ∑_(i,j)∈ℰ c^ℓ x_ij^ℓ + λmax_ξ∈𝒰 f(ξ, x)
    s.t.     ∑_i∈𝒩 x_i^p ≤Γ^p      p ∈𝒫
        x_i^d ≤Γ^d     i ∈𝒩
        x_ij^ℓ≤Γ_ij^ℓ    (i,j)∈ℰ
        x_i^d ∈ℤ^+, x_i^p, x_i^b, x^ℓ_i',j'∈ℝ^+      p∈𝒫,  i ∈𝒩, (i',j') ∈ℰ


Here the first-stage node-level decision variables include installed dispatchable generation capacity (x_i^d ∈ℤ_+), installed renewable plant capacity (x_i^p ∈ℝ_+) for renewable technologies p∈𝒫, and installed battery storage capacity (x_i^b ∈ℝ_+). Additionally, we consider transmission capacity (x_ij^ℓ∈ℝ_+) as a first-stage decision variable at the link level. Both installed dispatchable generation capacities and installed renewable plant capacities obey a system-wide resource availability constraint while installed transmission capacities obey a link-level resource availability constraint. Finally, max_ξ∈𝒰 f(ξ, x) denotes the worst-case recourse cost (i.e., economic dispatch cost given by (<ref>)), which is incurred with unit cost λ as part of the capacity expansion objective function. We “annualize” the worst-case recourse cost by setting λ = 365. For a given investment decision x and uncertainty realization ξ, the recourse cost is given by


    f(ξ,x) = min_y     ∑_t∈𝒯∑_i∈𝒩 c^f y_it^1 + c^s y_it^6 
    s.t.     y_it^1 + ∑_j∈𝒩 y_jit^2 + y_it^3 + y_it^4 = ξ_it^d - ∑_p∈𝒫ξ_it^p x_i^p      i ∈𝒩, t∈𝒯
        y_ijt^2 + y_jit^2 = 0     (i, j) ∈ℰ, t∈𝒯
        y_ijt^2 ≤ x_ij^ℓ    (i, j) ∈ℰ, t∈𝒯
        -y_ijt^2 ≤ x_ij^ℓ     (i, j) ∈ℰ, t∈𝒯
        y_it^1 ≤ν x_i^d      i ∈𝒩, t∈𝒯
        y_it^1 - y_i,t-1^1 ≤κν x_i^d     i ∈𝒩, t∈𝒯
        y_i,t-1^f - y_it^1 ≤ -κν x_i^d     i ∈𝒩, t∈𝒯
        y_it^5 ≤ x_i^b      i ∈𝒩, t∈𝒯
        y^5_it - y^5_i,t-1 + y_i,t-1^4 = 0     i ∈𝒩, t∈𝒯
        y_it^3 - y_it^6 ≤ 0      i ∈𝒩, t∈𝒯
        y^1_it, y^5_it, y^6_it≥ 0     i ∈𝒩, t∈𝒯.


Here, the total dispatchable generation at node i in period t is denoted by y_it^1. y_ijt^2 denotes the inflow of power from node i to node j in hour t. y_it^4 denotes the discharge rate of the battery located at node i in hour t while y_it^5 denotes its total charge. Load shedding is denoted by y_it^6, which is assumed to be the positive part of y_it^3. ν denotes the nameplate capacity of the dispatchable plants while κ and κ respectively denote the maximum ramp-up and ramp-down rates for dispatchable generation. The objective function (<ref>) minimizes the combined cost of fuel and a carbon tax for dispatchable generation (with unit cost jointly denoted by c^f) as well as load shedding (with unit cost c^s). First-stage decisions x_i^d, x_i^p, x_i^b, and x_ij^ℓ parameterize the constraints of (<ref>). Constraints (<ref>) impose flow conservation at each node. Specifically, the constraint balances dispatchable generation, power inflows, nodal load shedding, and battery discharging with net load (i.e., demand minus total generation from renewables). Importantly, y_ijt^2 is negative if node j receives power from node i, which is captured by the equality constraint (<ref>). Constraints (<ref>) and (<ref>) impose line limits on power flows. Constraints (<ref>) impose limits on total dispatchable generation while constraints (<ref>) and (<ref>) limit ramping up and down of dispatchable generation. Constraints (<ref>) limits the total state-of-charge of batteries. Constraints (<ref>) links battery discharging or charging (taken to be the negative of discharging) rates to battery state-of-charge. Constraints (<ref>) ensure that only the positive part of load shedding incurs a cost.



















§ EXPERIMENTAL SETUP DETAILS



 §.§ Data Processing

To process the data, we remove components corresponding to solar capacity factors for nighttime hours and offshore wind capacity factors for landlocked nodes, both of which correspond to capacity factors of zero in all observations, which gives ξ∈ℝ^427. In implementing CCG, we also remove redundant (i.e., perfectly multicollinear) components so that the dataset of ξ observations has full column rank when defining the uncertainty set. We then re-introduce the redundant components as affine transformations of the retained components in the adversarial subproblem using equality constraints. Consequently, the effective dimensionality of 𝒰 is 349 while the dimensionality of ξ is 427. For AGRO, we only remove components that are constant (i.e., zero) and train the VAE on the original 427-dimensional dataset.



 §.§ Computational Details


VAE training. To obtain AGRO results, we train a 4-layer VAE and evaluate a range of latent space dimensionalities, L ∈{2,4,8,16}. Each hidden layer has 64 hidden units and uses ELU activations. All models were trained with the Adam optimizer on a batch size of 2048 for 10000 epochs.

Optimization details. For the CCG subproblem, we introduce trivial valid inequalities in the subproblem to reduce computational runtimes. To solve the adversarial subproblem for AGRO, we assume a step size of η=0.01 and terminate the subproblem when subsequent iterations of gradient ascent yield less than 0.001% change in cost or when 100 iterations have been performed. We perform at least I=3 initializations of the subproblem in each iteration of AGRO but perform additional initializations (up to a maximum of 10 total) if the solution to the adversarial subproblem does not increase costs over the current estimate of worst-case recourse costs (i.e., if f(ξ^i, x^*) < γ).

Computational resources. Optimization results for the AGRO subproblem are obtained using the Cvxpylayers package <cit.> while results for the AGRO and CCG main problems as well as the CCG subproblem are obtained using Gurobi 11.0 <cit.> with a mixed-integer optimality gap of 0.01%. All optimization and model training is performed on the MIT Supercloud system <cit.> using an Intel Xeon Gold 6248 machine with 40 CPUs and two 32GB NVIDIA Volta V100 GPUs.



 §.§ VAE Performance Metrics

We quantify sampling performance of the VAE using standard metrics for fidelity (precision and density) and diversity (recall and coverage). These metrics are defined by <cit.> as follows:

    precision   = 1/M∑_j=1^M 1_ξ̂_j∈manifold(ξ_1,…,ξ_N)
    density   = 1/kM∑_j=1^M ∑_i=1^N 1_ξ̂_j∈ℬ(ξ_i,NND_k(ξ_i))
    recall   = 1/N∑_i=1^N 1_ξ_i∈manifold(ξ̂_1,…,ξ̂_M)
    coverage   = 1/N∑_i=1^N 1_∃ j  s.t. ξ̂_j ∈ℬ(ξ_i,NND_k(ξ_i)),

where ξ and ξ̂ respectively denote real (N total) and generated samples (M total), 1 denotes the indicator function, NND_k(ξ_i) denotes the distance from ξ_i to its k-th nearest neighbor (excluding itself) in the dataset {ξ_1,…,ξ_N}, and manifolds are defined as

    manifold(ξ_1, …, ξ_N) = ⋃_i=1^N ℬ(ξ_i, NND_k(ξ_i)).

Precision and density quantify the portion of generated samples that are “covered” by the real samples while recall and coverage quantify the portion of real samples that are “covered” by the generated samples. All results in Table <ref> are obtained using k=5 and with M=N=1260.

