Chance-constraint method

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Revision as of 07:34, 14 December 2021 by Jlm592 (talk | contribs) (Added more information to the Theory/Methodology section; also did some slight modifications to the section's format)
Jump to navigation Jump to search

Authors: Anthony Pacheco, Bryan Bausinger, John Maher, Martin Lis, Trevor Spaulding (SYSEN 5800 Fall 2021)

Introduction

The chance-constraint method of optimization programming is a process for working with random parameters within a problem while guaranteeing a certain performance. Uncertain variables in a project lead to questions regarding reliability and risk which make for difficulties in determining the most likely result. In stochastic optimization, expected or nominal values are used for these uncertainties. While there is some risk in making these stochastic optimization decisions, they are usually considered standard since they were already previously accounted for; a known "penalty". In practice, however, these penalties are not always known entities, such as extreme weather events. In these unknown cases, it is still important to plan for these events to occur and make certain decisions around them. A common line of thinking here is to allow for certain unexpected events that violate specific constraints as long as the overall constraint satisfaction is maintained with a given level of probability. In other words, certain levels of feasibility are guaranteed and these are defined as chance constraints. For example, a distributor may guarantee a certain amount of product will be delivered while taking into account certain chance constraints such as: weather events, supply chain issues, and/or a flat tire on a delivery truck. A system's performance can be optimized with uncertain constraints via the chance-constraint optimization method by accounting for these constraints and ensuring they satisfy some well-defined reliability values.[1][2]

Theory/Methodology

The chance-constrained optimization method was first created by Charnes, Cooper, and Symmonds in 1958-1959 relating to financial planning optimization. Over the years, improvements have been made to the chance-constrained optimization theory and computation processing methods, most notably by András Prékopa.[2]

General Form

A general form of a chance constraint is shown below:

This chance constraint formulated above is considered to be a constraint within an optimization problem where this is some objective function - usually denoted by - that is meant to be minimized.

Compared to a conventional optimization problem, the chance-constrained optimization problem differs due to the left-hand side inequality above because it is rarely provided explicitly. Therefore, there is not a general solution approach for chance-constrained optimization problems. The random and decision variables in the above equation can guide the path to solution via a linear programming solution, but not always. The wide ranging possibilities of the random variable (sometimes called the random vector) play the largest role in the difficult nature of the chance-constrained optimization problem.[1]

Joint vs. Individual Chance Constraints

The chance constraint above can be written more explicitly as:

This is called a joint chance constraint (or sometimes a separate chance constraint,[2]) because the entire probability covers the entirety of the inequality. In simpler terms, the entire constraint is considered as a whole. On the other hand, if each of the constraints in the system need to be considered individually, the chance constraint becomes a single constraint, which is formulated below:

This type of constraint is known as an individual chance constraint (and sometimes as a single chance constraint,[2]).

The benefit of working with the this latter individual chance constraint is that it is generally easier to solve because each of the inequalities are solved independently. However, in a system with a large amount of constraints, this generates an equally large amount of inequalities due to the one-to-one ratio with individual chance constraint relative to the single inequality within the joint chance constraint. This is therefore one of the pros of working with joint chance constraints as there is solely one inequality to work with as that inequality defines all of the constraints within the system. Although in comparison to the individual chance constraint, the joint chance constraint is normally more difficult to solve numerically because the system has to be considered as an overall whole instead of partwise.[1]

Numerical Example

To explain chance constraints in a simplified example, consider a refinery that is able to take two raw materials (, ) and simultaneously produce two different goods (prod1, prod2). To understand the production costs (), the generated outputs must be related to the amount of raw material it took to produce (, ). Additionally, the demand for each product generated (, ) and the production capacity () based on the constraints of the refinery must be understood. Below is a condensed table with the production constraints and costs as well as a formulation of these constraints as a linear program.

Products
Raws prod1 prod2 c b
raw1 2 3 2 1
raw2 6 3 3 1
relation =
h 180 162 γ 100

,

,

,

,

.

Graphing the objective function and constraints allows for us to immediately see the feasible region where all constraints are satisfied.

[Chart to be added]

Visually analyzing the feasible region, it can be concluded that the following is the optimal solution to the problem:

This is an oversimplification of this problem as all the variables are assumed to be fixed. For example, although the unit cost of the raw materials may be understood, these can be affected by natural disasters (fires or hurricanes destroying materials, supply chains disrupting supply/demand), politics (sanctions) and other factors. Although these macro events may have little impact on immediate material costs, it lowers the probability that your assumption of a fixed price will be accurate. More impactfully, demand of the various products is more difficult to predict and therefore has higher uncertainty. Additionally, the production capability at any given time is not fixed. For example, there may be issues with machines (repairs, calibrations etc..) or even the machine operators (illness, vacation resulting in not enough operators to run all machines at full capacity). To make this problem more realistic, let's assume:

  • Productivities of prod1, prod2 vary randomly
  • Weekly demands , vary randomly
  • Before manufacture, weekly production plan is fixed and actual production of prod1, prod2 can only be measured during production
  • Clients expect actual demand to be satisfied

The more simplistic linear program defined above now turns into a more complex stochastic linear program:

,

,

,

,

.

Adjusting the value of based on a desired confidence interval, the effect that on the feasible region can be seen.

[Chart to be added]

The difficulty in implementing a problem like this is that a production plan must be determined based off of the uncertainty of the situation, and how much risk one is willing to accept. There does exist a “safe” solution, in which the feasible region is determined based on the requirements to satisfy every constraint, even at different probabilities.

[Chart to be added]

Although this may be the safest solution, it may not be optimal as you may procure not enough raw materials to meet demand that exceeds your “safe” solution. Additional complexities and optimizations can be considered to improve the optimized solution but will be omitted for this example.[3]

Applications

The chance-constraint optimization approach can be extremely beneficial in any application where there are unknown variables, but with probabilities that can be associated with each variable. Some examples of real-world applications are as follows:

Stock Portfolio

Chance-constrained methods are often used as a risk aversion technique for designing a stock portfolio. Within this method, there is a general predicted value for the final wealth and an associated probability of survival to this method.[4]

Utility Demand (Power/Gas/Water)

Energy creation, particularly in renewable sources, has inherently high variabilities within examples such as solar or wind. It is no longer possible to fully predict energy generation as in the past. Therefore, there is a need for a probabilistic model to provide and distribute energy to all homes to a sufficient certainty. Hu et al. analyzes the economic dispatch of wind energy to meet the dispatch needs in very large instances using the chance-constraint approach.[5]

Transportation

Intermodal Freight Transportation (IFT) is the transportation of a material from one place to another involving at least two medians of transportation (i.e.. sea, air, road). Each of the shipping modalities contains its own stochastic factors such as priority, travel time, and availability. IFT provides the opportunity for faster shipment times, lower costs, improved throughput, and broader market availability. Zhao et al. modeled a two-stage chance-constrained approach with the stages being sea and rail, respectively. A network of available stations (rail), seaports (sea), and hubs (both) is modeled to create the available paths for goods. Their research shows the chance-constrained methods allows for different optimal service conditions. The probability in durations permitted late cost incorporations and more variability in design.[6]

Water Reservoir Management

Clean, unpolluted water has become a more scarce resource within recent years. To attack this issue, storage resources are designed in major cities such as Beijing, China to distribute water during demand periods. These demand periods vary with uncertainty and thus, the reservoir must be designed to distribute water to a satisfactory probability given all conditions. This model may explore impacts such as the season, pollution level, location of storage, and provide insight for future regulation.[7]

Conclusion

The chance-constraint method allows users to identify an optimized solution even when there are outstanding unknown risks within the process. The methodology incorporates variable volatility into the optimization constraints to attempt to account for this volatility. The user is able to identify what level of uncertainty is acceptable in the solution, which expands the region of available solutions that could be the optimum. However, when increasing the level of uncertainty, the user is also increasing the possible variation in the final answer due to the random variables. There are many different applications which benefit from the chance-constraint method. One of the most common industrial applications is in logistics planning which can range from power distribution, global transportation networks, and natural resource management.[5][6][7] By recognizing and preparing for unknowns in a problem, the chance-constraint method is a popular optimization process when dealing with uncertainties.

Sources

  1. 1.0 1.1 1.2 W. Ackooij, R. Zorgati, R. Henrion, and A. Möller, Chance Constrained Programming and Its Applications to Energy Management, 2011.
  2. 2.0 2.1 2.2 2.3 A. Geletu, M. Klöppel, H. Zhang, and P. Li, "Advances and applications of chance-constrained approaches to systems optimisation under uncertainty," International Journal of Systems Science, vol. 44, pp. 1209-1232, 2013.
  3. P. Kall, & S.W. Wallace, Stochastic Programming, pp. 10-20, 1994
  4. N.H. Agnew, R.A. Agnew, J. Rasmussen, and K. R. Smith, “An Application of Chance-Constrained Programming to Portfolio Selection in a Casualty Insurance Firm,” Management Science, vol. 15, no. 10, pp. 512-520, 1969.
  5. 5.0 5.1 Y. Hu, Y. Li, M. Xu, L. Zhou, and M. Cui, "A Chance-Constrained Economic Dispatch Model in Wind-Thermal-Energy Storage System," Energies, vol. 10(3), 2017.
  6. 6.0 6.1 Y. Zhao, Q. Xue, Z. Cao, and X. Zhang, "A Two-Stage Chance Constrained Approach with Application to Stochastic Intermodal Service Network Design Problems," Journal of Advanced Transportation, 2018.
  7. 7.0 7.1 W. Li, K. Jiao, Z. Bao, Y. Xie, J. Zhen, G. Huang, and L. Fu, "Chance-constrained dynamic programming for multiple water resources allocation management associated with risk-aversion analysis: A case study of Beijing, China," Water, vol. 9(8):596, 2017.