CS410 Homework 4: Constrained Optimization

# CS410 Homework 4: Constrained Optimization **Due Date: Friday, 2/28 at 11:59pm** **Need help?** Feel free post on [Edstem](https://edstem.org/us/courses/74300) for TA assistance. ## Assignment Overview Constrained optimization is one of the most widely applicable topics that we cover in this class. It has been around a lot longer than deep learning, and even with all the hype around the latter, it remains a fundamental tool driving every part of the world economy. From [planning air travel schedules](https://www.gurobi.com/case_studies/air-france-tail-assignment-optimization/) to determining the [NFL schedule](https://www.gurobi.com/case_studies/national-football-league-scheduling/), mathematical programs are used everywhere. In this homework, you will model and solve two specific problems that require constrained optimization: 1) risk management in investing and 2) planning a clean energy grid for the state of Rhode Island. You will do so using the python library CVXPY. In Part 1 of this homework, you will be tasked with choosing a *portfolio* of stocks to invest in. You will construct your portfolio to maximize expected returns while ensuring your risk remains below some acceptable threshold. In Task 1, you will derive an expression for risk. In Task 2, you will program a model that uses real historical stock data to make purchasing decisions. Then, having made sound investment decisions, you will work on planning the transition to renewable energy for the state of Rhode Island. Rhode Island has an ambitious [law](https://www.ncelenviro.org/articles/rhode-island-enacts-100-renewable-energy-by-2033-standard/) that requires 100% of electricity used in the state to be generated by renewable energy sources by 2033. Rhode Island has the ability to generate renewable energy through wind farms and solar panels. However, there are times of the day when the sun doesn't shine and the wind isn't blowing. What then? Most people wouldn't accept blackouts whenever the sun stops shinning or the the wind stops blowing. How can we maintain reliability even with variable renewable energy generation? The answer is energy storage, e.g., batteries, hydrogen, etc. But how many solar panels, windmills, and batteries will we need? In Part 2 of this homework, you will use real wind, solar, and energy demand data for the state of Rhode Island to optimize for a least-cost solution to this problem. ### Learning Objectives What you will know: - What covariance is and why it is important - What Mathematical Programming is and why it is important to real world applications. What you will be able to do: - Model an optimization problem in terms of decision variables, objective function, constants (given by the data), and constraints - Use the CVXPY library to translate mathematical formulations of optimization problems into Python ## Mathematical Programming The field of mathematical programming studies finding solutions to constrained optimization problems. Constrained optimization problems consist of two components, an objective and a set of constraints. We can write the general formulation of a mathematical program as: $$\text{objective:} \qquad \min_\vec{x} f_0(\vec{x})$$ $$\text{constraints:}\qquad \text{s.t.}\quad f_i(\vec{x}) \geq b_i$$ Where the vector *$\vec{x}$* is the vector of *decision variables*, $f_0(\vec{x})$ is the *objective function*, and $f_i(\vec{x}) \geq b_i$ are *constraints* that restrict the feasible values of $\vec{x}$. The goal of mathematical programming is to find an optimal feasible solution $\vec{x}^*$ that satisfies the constraints and has the best objective value possible for feasible solutions. Mathematical programming typically consists of two stages: 1) Modelling your problem: Actually formulating your real world problem into formal mathematical language that matches the requirements of mathematical programming. 2) Solving your problem: Given a mathematical program, find the optimal solution. In this homework (and course) we focus entirely on the problem of modelling and use off-the-shelf solvers to solve our formulations. If we let our objective and constraints be any possible functions, you can imagine that we could make mathematical programming arbitrarily hard. Mathematical programming is, in fact, in the set of NP-Complete problems, which are problems that we (very) strongly suspect are hard to solve. There are a few cases where we know that mathematical programming is "relatively easy". 1. When $f_0$ and all $f_i$ are *linear* functions. These types of problems are referred to as Linear Programs (LPs) 2. When $f_0$ is convex and the feasible set of solutions created by the constraints is also convex. These types of problems are called Convex Programs. ### Linear Programs A linear function $f(\vec{x})$ is one that can be written as the sum of each element $x_i$ of $\vec{x}$ times some coefficient $w_i$: $$f(\vec{x}) = w_1x_1+ w_2 x_2 +\ldots+w_n x_n$$ Each function in our program (objective and each constraint) will take on this form. By convention, we denote the coefficients of the cost function as $c$ (for "cost"), the coefficients on the left hand side on the constraints as $a$, and the right hand side of the constraint as $b$. Linear programs therefore take the form: $$\min_x \quad c_1x_1 + \ldots + c_n x_n$$ $$\text{s.t.} \quad a_{j1} x_1 + a_{j2} x_2 + \ldots a_{jn}x_n \geq b_j \quad \forall j$$ We can more compactly express LPs if we use vector and matrix notation. Using $\vec{c}$ as the vector of all $c_i$ and $\vec{a_j}$ as the vector of all $a_{ji}$. $$\min_x \quad \vec{c}^T \vec{x}$$ $$\text{s.t.} \quad \vec{a}_j^T \vec{x}\geq b_j \quad \forall j$$ Finally, we can further simplify our notation by creating a matrix $A$ where the rows of $A$ are the corresponding $\vec{a}_j$, $$A= \begin{bmatrix} \vec{a}_1^T\\ \vec{a}_2^T\\ \vdots\\ \vec{a}_m^T \end{bmatrix}$$ Every linear program can be represented as a problem with constants $\vec{c}, A, \vec{b}$ and decision variables $\vec{x}$ as: \begin{align} \min_\vec{x} \quad &\vec{c}^T \vec{x}\\ \text{s.t.} \quad &A\vec{x} \geq \vec{b} \end{align} ### Convex Programs Linear programs can be used to solve many types of real world problems, but they do restrict decision variables to have a linear relationship with each other. Take for instance the problem of finding $x_1, x_2$ with the smallest value of $x_1 + x_2$, while restricting $x_1$ and $x_2$ to lie in a circle of radius 1 around the origin: \begin{align} \min \quad &x_1+x_2\\ \text{s.t.} \quad &x_1^2 + x_2^2 \leq 1 \end{align} This problem is not a linear program because it involves higher order terms (i.e., $x_1^2, x_2^2$) in the constraint. This program is a *convex program*, not a linear program, because the constraint set is convex (a circle is convex). For a period of history, it was thought that convex programs were much harder to solve than linear programs. However, advances in optimization theory and algorithms, particularly the development of interior point methods in the 1980s, showed that convex programs can often be solved nearly as efficiently as linear programs. Today, we have powerful solvers that can handle both linear and convex programs effectively. In this assignment, you will write both a linear program and convex program. ## CVXPY We will be using the CVXPY library in this assignment to code our problems into Python. CVXPY is a library that helps you encode your problem formulation and then passes this encoding to another library to solve. There are currently [26 different compatible solvers](https://www.cvxpy.org/tutorial/solvers/index.html#choosing-a-solver) to choose from. Each has its own unique syntax, idiosyncracies, and other issues, but by using CVXPY, we can switch between solvers seamlessly. In this assignment, you will use CVXOPT, the default solver for CVXPY. ::: warning CPLEX and Gurobi are the most common solvers for industrial applications. Gurobi and CPLEX are faster than current open source solvers for a variety of problems, but require licenses to use. The academic license for Gurobi is free. The paid version is $10,500, which should give you some idea of how valuable mathematical optimization truly is. ::: To help you learn the syntax and style of CVXPY, we provide a number of examples in `cvxpy_examples.py`. These are the examples covered in class and in the lecture notes and should help you familiarize yourself with the process of translating your mathematical problem formulations to code. We have included formulations for: (1) The manufacturing problem with raw material constraints (2) The dieting problem (3) Optimal Control of a rocket For each example (when appropriate), we provide an example with for loops, as well as a vectorized example using matrices and vectors to store our data and decision variables. ## Stock Portfolio Optimization Around 60\% of all Americans own stock in some form, either by purchasing stocks directly, by purchasing mutual funds, by saving money in a retirement fund, etc. Why do people invest in the stock market rather than keep all their money in a checking account or under their mattress? Stocks, on average, tend to grow at a faster rate than interest. The value of the S&P 500 (a collection of stocks) has grown on average 10% each year for the past 50 years. If you (or your parents) had put $1,000 in the S&P 500 in 1990, your investment would be worth $44,000 today (or $12,000 if you account for inflation)! So what is the downside? The stock market is not a risk-free investment opportunity, like leaving your money in the bank to collect interest. The market has trended upward on average, but it is not guaranteed to go up every year. There is a *risk* that the value of your investment crashes, and this risk varies from stock to stock. Over the past 6 months the value of Gamestop has increased more than the value of Apple stock (From July 2024 to January 2025), however the value of Gamestop stock can vary wildly day to day. Surely investing in Apple is much less riskier than investing in Gamestop! All investors in the stock market take on some amount of risk, but some investors may be willing to take on more risk than others. In this first part of the assignment, you will focus on the problem of *portfolio optimization*. Given a fixed amount of funds, some amount of tolerable risk, and historical information on stock prices, what is portfolio of stocks should can buy to maximize your returns? ### Your Problem You have come into a large sum of money recently from an undisclosed activity which you are somewhat secretive about, perhaps 45.6 Billion Won. You'd like your money to grow in the future to save for retirement, where you expect eggs to cost $1,000 a carton. Despite taking risks to acquire your initial cash fund, you now find yourself risk averse and would like to avoid the possibility that you lose a significant portion of your original investment. So you seek to invest in a portfolio of stocks that meets your risk threshold while still maximizing your expected return? Is that an objective that you are optimizing with a constraint? Lightbulb moment. You know that if you can formulate this problem as a convex optimization problem, you can solve it with CVXPY. To do this you need to determine: 1. What data define your constants? 1. What are your decision variables? 1. What is your objective function? 1. What are the constraints? The decision in this case is how to divvy up your funds across the various stocks: i.e., how much weight to assign to each stock. Each of these weights represent a fraction of your budget and therefore the sum of these weights should not be larger than 1. The objective is the total return, which is the weighted sum of each stock's return. The weights of this weighted sum are how much of your portfolio each stock makes up. The main constraint is that the risk of your investments must remain below some maximum risk threshold. In Task 1, you will derive the expression for the variance and risk of your portfolio, and then in Part 2, you will formulate this problem as a constrained optimization problem and solve it. ### Quantifying Risk In [Modern Portfolio Theory (MPT)](https://en.wikipedia.org/wiki/Modern_portfolio_theory) the risk of a portfolio is measured in its terms of the historical sample variance. Sample variance is a measure of how far a set of numbers are from their average. Take the example below with two potential stocks, a red stock with high variance and a blue stock with low variance. They both start and end at the same point. Which stock would you rather own? (Which one would allow you to sleep better at night?) ![Screenshot 2025-02-14 at 10.31.03 PM](https://hackmd.io/_uploads/Sk8K9KaKyg.png) If we had stopped measuring performance slightly earlier (at 9.9 instead of 10), the red stock would have appeared better. If we had stopped measuring still earlier, at 9.6, the red stock would have appeared worse. The red stock has higher variance, sometimes outperforming the blue stock and sometimes underperforming it. The red stock has more risk associated with it. Can you see why variance is a measure of risk? MPT assumes that the risk of investments in the future is informed by their historical behavior. Computing the variance of a single stock is straightforward. However, portfolio optimization involves multiple stocks, which complicates things. What if we purchase 1 unit of the blue and red stock below? ![Screenshot 2025-02-20 at 1.41.55 PM](https://hackmd.io/_uploads/BkQYwgS5kx.png) If we add together these two stocks, which individually have high variance, actually get a constant output of 0, which has 0 variance. Stock price trends cannot be treated as independent. To express the risk of a sum of dependent variables and the variance of your portfolio, you will need to consider how these variable vary relative to each other, or their covariance. You will derive the expression for computing the variance of such a portfolio in Task 1. ## The Data The dataset of historical stock prices comes from [this source](https://www.kaggle.com/datasets/nelgiriyewithana/world-stock-prices-daily-updating) on Kaggle. You can inspect the dataset by looking at `World-Stock-Prices-Dataset.csv`. The dataset on the web updates daily. The data you are working with locally was downloaded on 2/8/2025 and only contains data up until 2/7. The historical data provided to your implementation will be for the past year. Looking farther back in time will provide more reliable estimates of variance and returns, but missing values and other discrepencies start to appear in the data. For this assignment, we make some simplifying assumptions about stocks during preprocessing. 1) We do not account for dividends. Dividends are a payment you can receive for owning a stock. After a company makes profit, they can choose to return some of that profit to the shareholds as a dividend. 2) Some stocks in the original dataset are missing closing prices for some days in the year (for whatever reason). We filter these stocks out and do not include them in the dataset. When calculating covariance between two stocks, they are required to have the same number of observations. 3) We normalize the prices of each stock by the price of the stock one year before the dataset ends. If stock A starts at $200 and ends at $300 dollars and stock B starts at $20 and ends at $30, you can achieve the same returns by buying 10 stocks of B instead of 1 stock of A. We normalize all prices to start at $1, in which case both stock A and B starts at 1 and ends at 3. ## Tasks The goal of this section is to figure out how to compute the variance of a sum of random *dependent* weighted variables, corresponding to the risk of your portfolio. The first set of tasks guides you through the derivation of this expression. Let $w \in \mathbb{R}$ be a scalar multiplier and $x$ be a sample variable with $m$ observations $\{x_1, x_2, \ldots ,x_m\}$. We give you the following properties: 1. $w\cdot x = \{wx_1, wx_2, \ldots, wx_m\}$ (Applying a weight to $x$ would apply it to each observation) 1. $\mu(x) = \frac{1}{m} \sum_{i=1}^m x_i$ (Definition of the *sample mean*) 1. $\sigma^2(x) = \frac{\sum_{i=1}^m (\mu(x) - x_i)^2}{m}$ (Definition of the *sample variance*) :::info **Task 1a**: Variance of scaled data Prove $\sigma^2(w\cdot x) = w^2\cdot \sigma^2(x)$ using properties 1, 2, and 3. Write your proof in your `README`. You may also upload a pdf of a handwritten document if you prefer, just write the name of the file in your `README` as well. ::: Now, we turn our attention to the case of $n$ *independent* stocks $\{x^{(1)}, x^{(2)}, \ldots, x^{(n)}\}$. Each $x^{(i)}$ will have $m$ historical observations $\{x^{(i)}_{1}, x^{(i)}_{2}, ... x^{(i)}_{m}\}$. :::info **Task 1b** Variance of a Sum of Scaled Random Variables Prove the following property of the variance of a sum of $n$ weighted *independent* random variables: $$\sigma^2 \left[ \sum^n_{i=1} w_i x^{(i)} \right] = \sum_i^n w_i^2 \sigma^2(x^{(i)}) $$ ::: For a pair of random variables $x^{(1)}, x^{(2)}$, we define the *sample covariance* $\text{cov}$ between $x^{(1)}, x^{(2)}$ as follows: $$\text{cov}(x^{(1)}, x^{(2)}) = \frac{1}{m}\sum_{i=1}^m((x^{(1)}_{i} - \mu_1)(x^{(2)}_i - \mu_2))$$ Following our aforementioned convention, $x^{(1)}_i$ refers to our $i$th observation of variable 1. :::info **Task 1c** Covariance of Weighted Random Variables Show that $\text{cov}(w_1x^{(1)}, w_2x^{(2)}) = w_1\text{cov}(x^{(1)}, x^{(2)})w_2$ ::: Covariance is defined for pairs of random variables. Assuming $k$ random variables, we can organize the covariances among all pairs of these $k$ variables in a covariance matrix. Here is an example when $k=3$. $$\Sigma = \begin{pmatrix} \text{cov}(x^{(1)}, x^{(1)}) & \text{cov}(x^{(1)}, x^{(2)}) & \text{cov}(x^{(1)}, x^{(3)}) \\ \text{cov}(x^{(2)}, x^{(1)}) & \text{cov}(x^{(2)}, x^{(2)}) & \text{cov}(x^{(2)}, x^{(3)}) \\ \text{cov}(x^{(3)}, x^{(1)}) & \text{cov}(x^{(3)}, x^{(2)}) & \text{cov}(x^{(3)}, x^{(3)}) \end{pmatrix}$$ The entry $\Sigma_{ij}$ in the matrix $\Sigma$ at row $i$ and column $j$ corresponds to $\text{cov} (x^{(i)}, x^{(j)})$. :::warning **Note:** We typically denote the covariance matrix by $\Sigma$. Sigmas are also used for sums. Hopefully, the meaning will always be clear to you from context! ::: It should be clear to see from the definition of covariance of a variable with itself is exactly that variable's variance. That is: $\text{cov}(x^{(1)}, x^{(1)})=\sigma^2(x_1)$. We now present an additional property of *dependent* random variables: 5) The sum of two *dependent* variables has variance: $\sigma^2(x^{(1)} + x^{(2)}) = \text{cov}(x^{(1)}, x^{(1)}) + \text{cov}(x^{(1)}, x^{(2)}) + \text{cov}(x^{(1)}, x^{(2)}) + \text{cov}(x^{(2)}, x^{(2)})$ We can compute the variance of the sum of $x^{(1)}$ and $x^{(2)}$ by simply summing the elements of their covariance matrix. More generally, for $n$ random variables, this sum can be written as $\Sigma_{i=1}^n \Sigma_{j=1}^n \Sigma_{ij}$, or more compactly as a matrix multiplication $\vec{1}^T\Sigma\vec{1}$, where $\vec{1}$ is a vector of $n$ 1's. :::info **Task 1d** Consider a set of $n$ stocks $\{x^{(1)}, x^{(2)} \ldots x^{(n)}\}$ with covariance matrix $\Sigma$. You would like to calculate the variance of the portfolio that results from you buying $w_i$ amount of stock $x_i$, for all stocks. Show that $\sigma^2(\sum_{i=1}^n w_ix^{(i)}) = \sum_{i=1}^n \sum^n_{j=1} w_i \text{cov}(x^{(i)}, x^{(j)}) w_j$. ::: The property you prove in this task can be more compactly expressed using matrices and vectors as $\sigma^2(\vec{w}^T\vec{x}) = \vec{w}^T \Sigma \vec{w}$, and is the total variance (risk) of your portfolio. ### Implementation :::info **Task 2a** Conceptual: Problem formulation What are the decision variables, cost function, and constraints for the portfolio optimization problem described above? What are the constants for your problem? Write your answers in your `README` (or handwritten document). Your answers should be mathematical expressions and use the variables and constants you define in mathematical expressions. ::: Your problem formulation in Task 2a probably uses covariance and the historical returns of each stock in some way. Your first implementation task of this homework is to find these quantities given historical stock data. :::info **Task 2b** Measuring Risk Implement the `calculate_stats` method in `portfolio_optimization.py`. This method takes as input historical stock data for a collection of stocks and outputs the average return and covariance of the stocks. ::: After computing these values, you are ready to actually implement your model in Python! You can reference examples from the course notes and `cvxpy_examples.py` to see how we can convert mathematical formulations directly into Python code. :::info **Task 2c** Implement the `build_model` and `solve_model` methods in `portfolio_optimization.py`. In `build_model`, you will construct a CVXPY `Problem` out of an objective function and constraints (i.e., your formulation). In `solve_model`, you will call `problem.solve` and format the results into a dictionary. ::: You can run `python portfolio_optimization.py --risk 1e-4` to run your program with a maximum risk of $1\times 10^{-4}$. The variance you are using is with respect to daily price changes on stocks normalized to start at $1, which means the variance of each stock and covariances of pairs of stocks are all small numbers. :::warning **Note:** Make sure to test your code for each of your functions implemented above. You should be unit testing your code regardless of whether we ask for it explicitly; it’s good practice (and may help you catch some hidden tests :D ) ! ::: :::info **Task 2d** Try four different values of risk tolerance and report your results in your README. Be sure to choose four values that produce four different results! What trends do you notice as risk tolerance decreases (1--2 sentences)? Why might diversification be beneficial when making investment decisions? (1--2 sentences) Select one of the results and look up the stock names of a few of the stocks with non-zero weights if you haven't heard of them before. What companies does your model recommend you invest in? Is there a risk tolerance that makes your model not want to purchase any stocks (e.g., weights are None)? Why might the solver be able to find a set of weights that meets that risk threshold? (1--2 sentences) ::: ## Energy System Planning for Rhode Island In the second part of this homework, you will implement a [Macro Energy Model](https://www.cell.com/joule/pdf/S2542-4351(19)30361-7.pdf) for the state of Rhode Island. Your model will seek to gain insights into what portfolio of energy storage technologies could be best for our state given its specific weather and electricity demand needs. Macro Energy System Modelling is an active area of research and is being used to inform clean energy plans at the state level. You can view Rhode Island's current grid portfolio [here](https://energy.ri.gov/renewable-energy/ris-clean-energy-portfolio). In this homework, you will only model two sources of electricity generation, solar and (on-land) wind. While there are many other electricity generation technologies available (e.g., natural gas, nuclear, off-shore wind, hydro, etc.), you will use wind and solar because these are the most widely available renewable resources across the country and the most interesting to model due to their variability. This assignment closely follows a series of Macro Energy Modelling papers on similar subjects. The data you will use has been provided by Anna Li and Jackie Dowling and the model you will build is a simplification of [their paper](https://pubs.acs.org/doi/10.1021/acs.est.3c10188) [1]. [1] Li et al. "The Influence of Regional Geophysical Resource Variability on the Value of Single- and Multistorage Technology Portfolios" in Environmental Science & Technology. 2024. [(Macro-Energy Modelling Github)](https://github.com/carnegie/MEM_public/tree/master) ### Energy Storage Energy systems that rely on variable renewable energy sources need some type of energy storage system to provide reliable electricity. This stored energy can be used when there are gaps in the energy produced by renewables (e.g., when there is no wind or sun available for windmills and solar panels). Batteries are energy storage technologies. Small phone batteries can be charged overnight, and then used during the day to run your phone. Larger batteries can work at a much larger scale, powering parts of an electrical grid. You will model two different types of batteries in this homework: lithium ion batteries and metal-air batteries. Metal-air batteries are a new type of energy storage technology with promising properties for grid-level storage. In this assignment, you will work with cost and efficiency numbers from the metal-air batteries developed by [Form Energy](https://formenergy.com/technology/battery-technology/), a company based in nearby Somerville, Massachussets. There are three main features of energy storage technologies that could affect your model. 1) Efficiency: How much of the energy put into storage is retrievable? No energy storage processes are 100% efficient; some energy is always lost in the storage process. Litium ion (Li-ion) batteries at grid-scale have a round-trip energy efficiency of around 86%. This means that 86% of energy put into storage in a li-ion battery can be retrieved. Metal-air batteries are much less efficient, with a round-trip efficiency of 46%. 1) Cost: How much does money does it cost to store energy? Traditional Li-ion batteries are efficient, but they are also expensive. A Li-ion battery large enough to store one megawatt-hour of energy can cost upwards of $300,000. The equivalent metal-air battery costs around $2,500. 1) Duration: The duration of an energy storage technology refers to how long an energy storage technology can discharge at its maximum discharge rate before depleting. Li-ion batteries have a duration of 6 hours or less. Metal-air batteries can have a duration upwards of 100 hours. This is an important property of batteries to model, but you will not model it in this assignment (you're doing so much already). Given the different cost and efficiencies of these technologies, which storage technology will be a better fit for Rhode Island? Will one technology dominate the other or will a balance between the two be the best option? Which technology should Rhode Island invest in long term? You will investigate this question by building and solving linear programs. ### The Data You will be given three sources of data to incorporate into your model. Each of the provided data sources provide *hourly* data for one entire year (2019). 1) Demand: The amount of energy needed for consumption. If the amount of demand exceeds the amount of generation and energy stored, then there will be a blackout and loss of power. 1) Solar Capacity Factors: How "sunny" it is. If the capacity factor is 0, your solar panels will not generate any electricity (e.g., it is nighttime). If the capacity factor is 1, then your solar panels will generate electricity at full capacity (e.g., it is sunny out). If the capacity factor is 0.5, then your solar panels will work at 50% efficiency and generate half their full capacity. 1) Wind Capacity Factors: Similar to solar capacity factors, these measure how "windy" it is and how much energy your windmills can generate. 1) Costs of each technology: How much does each technology cost? This isn't as straightforward as looking up an item panel on Amazon and looking at the price. These technologies have long lifespans (e.g., 30 years) and the price of purchasing them should be *amortized* (spread over those 30 years). The costs provided to you have been amortized already and processed to be in proper units ($/kW for energy generation and $/kWh for energy storage). We provide a simple test case in `unit_tests.py` as well as real wind/solar/demand data for Rhode Island. We have provided the code to process and load the Rhode Island data. ### The Model **The constants**: The demand and capacity factors described above are constant. No matter how much wind and solar you purchase, the demand and the weather will not change. The cost of each technology is constant as well. **The decision variables**: The amount (the capacity) of each energy generation technology and each storage technology purchased are decisions that are being optimized for. There is one more set of variables required for your model: How much energy is stored in each technology at each timestep. These values will *change* based on how much of each storage is needed, and are therefore variables in your optimization problem. You may find adding additional variables, such as how much energy is added to storage at each timestep and how much is withdrawn can make your expressions easier to write. **The objective**: The objective is to minimize the overall cost of the system (i.e., save taxpayer money). The costs provided have units $/kW for energy generation and $/kWh for energy storage. The amount of energy generation capacity has units kW, meaning you can multiply the amount of solar you build times the cost of solar and you will be left with total amount of money spent on solar. The cost of energy storage, is a bit more complicated. You have decision variables for how much energy is stored at each timestep. If at some point your model stores 200 kWh in storage, you need to have purchased that much storage. You will need an additional variable to keep track of the maximum amount of energy stored at any single timestep. Note, the maximum of a set of numbers $x_i$ is the smallest number $x_{max}$ such that $x_{max} \geq x_i \quad \forall i$, perhaps you can express this in... **The constraints:** The electricity grid must meet demand at every hour throughout the year. If RI does not generate enough energy or have enough in storage to cover the gap, then there are serious problems. That can be expressed as Energy Generated + Energy Withdrawn from Storage $\geq$ Demand. If there is excess energy generated at a timestep, it can be placed into storage: Energy Generated - Demand $\geq$ Efficiency * (Energy Put into Storage). Note that our efficiency values apply when energy is put into storage, you will get different results if you apply efficiency when taking energy out of storage. You will have to slightly adjust these expressions to take into account the fact that there are two energy storage technologies you can store energy in at any time step. There will be additional constraints on the signs of variables and perhaps a constraint to compute the maximum amount of storage used. ## Tasks You will now formalize all of the above into a linear program. **You will be asked to provide your formulation before asking any questions in hours or on Edstem about code.** Much of the hard work has been done to put costs and efficiency into units that make your life easy. For instance, the cost of solar generation is in dollars per killowatt hour ($/kWh), meaning how much money it will it take to generate 1 kW in an hour. Demand is in kW for each hour. :::info **Task 3a** Formalize the energy planning problem as a linear program. You are given wind and solar capacity factors for each hour $t$ in a year $f^w_{t}, f^s_{t}$ respectively, demand data $D_t$, cost of wind, solar, Li-ion batteries, and metal-air batteries $c_w, c_s, c_b, c_m$ respectively, and the efficiency of each storage $\eta_b, \eta_m$. i) What are the decision variables for your problem? Describe your notation in english first. ii) What is the objective function? iii) What are the constraints? iv) What are the sign constraints? Can any of your decision variables be negative? Write your answer in your README. You may also upload a handwritten version as a pdf, so long as your handwriting is legible. Please indicate you have done so in your README and include the filename of that pdf. ::: :::info **Task 3b** Implement the `build_and_solve_model` method in `energy_planning.py` This method builds a CVXPY problem and solves it, returning values for the amount of generation and storage built, as well as the amount of energy stored each hour of the year in both storage technologies. You can run your model on the real world data by running ```python energy_planning.py --fraction_of_year 1.0``` You can adjust the fraction of the year to be smaller if you'd like it to run faster for testing. ::: :::warning We have provided unit tests for incremental testing in `unit_tests.py`. You should incrementally build your model, starting with only solar and wind generation, then adding Li-ion batteries, then adding metal-air batteries. These are not an exhaustive set of tests (i.e., the autograder has additional hidden tests). You should still create your additional tests to determine if your formulation is working as intended! ::: :::spoiler Hint: Relevant Example for Implementation We recommend you look at the optimal control example in the notes and `cvxpy_examples.py` for an example of how to handle constraints and variables for every timestep. a CVXPY `Problem` takes in a list of constraints, which can be built using for loops. Building the list of constraints will be easier than constructing a matrix $A$ such that $Ax\geq b$ is your only constraint. ::: :::info **Task 3c**: Look at the solution to your problem (e.g., solar and wind capacity, total amount of storage, etc.). How would you expect the objective value to change if we added additional sources of generation or storage? (1--2 sentences) What would you need to change with your model to add an additional type of generation technology, say natural gas, to the system. What if we wanted to constrain natural gas to only generate 10% of total electricity generated? Rhode Island has plans to reduce natural gas usage by 5-10% every year until the grid is fully renewable. How could we model these intermediate years? (2--3 sentences) ::: :::spoiler All the caveats You have created and solved a model for RI's energy future. This is just a model and all model's are imperfect. We'll briefly describe some of the ways that this model is approximating reality. 1) Battery duration is not included and there is no constraint on how quickly batteries can discharge. In reality, metal-air and Li-ion batteries can serve different roles in grid-scale energy storage due in large part to this difference in duration. 1) We do not consider energy transmission and how you get energy from where it is generated to where it needs to be. 1) We assume all solar and wind costs and energy generated are the same. That means when our model says build $x$ number of windmills, all the windmills are built in the same place with the same wind conditions. This is maybe actually reasonable for Rhode Island, but would not work if we wanted to model larger geographical regions. 1) We do not model all generation and storage technologies. The most notable exception is off-shore wind, which currently generates 1/3 of Rhode Island's renewable energy. :::  ### Testing Code - `unit_tests.py`: Provide example tests for simple energy systems using wind and solar energy. You can and should add more tests to this file to verify your storage is working as intended. Can you construct an example where storage is required no matter how much wind and solar capacity is built? ## Submission ### Download Please click [here](https://classroom.github.com/a/H0BmBdGq) to access the assignment. ### Handin Your handin should contain the following: - all modified files, including comments describing the logic of your implementations, and your tests - and, as always, a README containing: - a brief paragraph summarizing your implementation and highlighting the outcomes of all tests - your solutions to any conceptual questions - known problems in the code - anyone you worked with - any outside resources used (eg. Stack Overflow, ChatGPT) ### Gradescope Submit your assignment via Gradescope. To submit through GitHub, use this sequence of commands: 1. `git add -A` 2. `git commit -m "commit message"` 3. `git push` Now, you are ready to upload your repo to Gradescope. :::danger **⚠️WARNING⚠️** Make sure you have the correct assignment repo and branch selected before submitting. ::: *Tip*: If you are having difficulties submitting through GitHub, you may submit by zipping up your hw folder. ### Rubric | Component | Points | Notes | |-------------------|----|--------------------------------| | Task 1: Variance and Covariance | 15 | Points awarded based on soundness, correctness, and readability of proofs.| | Task 2a | 15 | Points awarded for correct problem formulation and variable definitions.| | Task 2b | 5 | Points awarded for correctly calculating covariance and stock returns.| | Task 2c | 15 | Points awarded for correct implementation of model| | Task 2d | 5 | Points awarded for completing task as specified.| | Task 3a | 20 | Points awarded for correct formulation. Partial credit awarded for partially correct formulations| | Task 3b | 20 | Points awarded for correct implementation. Partial credit awarded for passing tests where just wind and solar are used (no batteries). Partial credit awarded for passing tests with just one energy storage technology (and wind and solar for generation). Full credit awarded for system that uses all technologies.| | Task 3c | 5 | Points awarded for completing task as specified. | :::success Amazing work! You've completed assignment 4! ![Screenshot 2025-02-21 at 10.21.58 AM](https://hackmd.io/_uploads/rkxS9zL91g.png)