Stochastic Optimization is a framework for modeling optimization problems that involve uncertainty. Many of the fundamental concepts are discussed in the linear case below.
Stochastic Linear Optimization
Introduction
The fundamental idea behind stochastic linear programming is the concept of recourse. Recourse is the ability to take corrective action after a random event has taken place. A simple example of two-stage recourse is the following:
- Choose some variables, x, to control what happens today.
- Overnight, a random event happens.
- Tomorrow, take some recourse action, y, to correct what may have gotten messed up by the random event.
We can formulate optimization problems to choose x and y in an optimal way. In this example, there are two periods; the data for the first period are known with certainty and some data for the future periods are stochastic, that is, random.
Example
You are in charge of a local gas company. When you buy gas, you typically deliver some to your customers right away and put the rest in storage. When you sell gas, you take it either from storage or from newly-arrived supplies. Hence, your decision variables are 1) how much gas to purchase and deliver, 2) how much gas to purchase and store, and 3) how much gas to take from storage and deliver to customers. Your decision will depend on the price of gas both now and in future time periods, the storage cost, the size of your storage facility, and the demand in each period. You will decide these variables for each time period considered in the problem. This problem can be modeled as a simple linear program with the objective to minimize overall cost. The solution is valid if the problem data are known with certainty, that is, if the future events unfold as planned.
More than likely, the future will not be precisely as you have planned; you don’t know for sure what the price or demand will be in future periods though you can make good guesses. For example, if you deliver gas to your customers for heating purposes, the demand for gas and its purchase price will be strongly dependent on the weather . Predicting the weather is rarely an exact science; therefore, not taking this uncertainty into account may invalidate the results from your model. Your “optimal” decision for one set of data may not be optimal for the actual situation.
Scenarios
Suppose in our example that we are experiencing a normal winter and that the next winter can be one of three scenarios: normal, cold, or very cold. To formulate this problem as a stochastic linear program, we must first characterize the uncertainty in the model. The most common method is to formulate scenarios and assign a probability to each scenario. Each of these scenarios has different data as shown in the following table:
| Scenario | Probability | Gas Cost ($) | Demand (units) |
|---|---|---|---|
| Normal | 1/3 | 5.0 | 100 |
| Cold | 1/3 | 6.0 | 150 |
| Very Cold | 1/3 | 7.5 | 180 |
Both the demand for gas and its cost increase as the the weather becomes colder. The storage cost is constant, say, 1 unit of gas is $1 per year. If we solve the linear program for each scenario separately, we arrive at three purchase/storage strategies:
- Normal – Normal
| Year | Purchase to Use | Purchase to Store | Storage | Cost |
|---|---|---|---|---|
| 1 | 100 | 0 | 0 | 500 |
| 2 | 100 | 0 | 0 | 500 |
Total Cost = $1000
- Normal – Cold
| Year | Purchase to Use | Purchase to Store | Storage | Cost |
|---|---|---|---|---|
| 1 | 100 | 0 | 0 | 500 |
| 2 | 150 | 0 | 0 | 900 |
Total Cost = $1400
- Normal – Very Cold
| Year | Purchase to Use | Purchase to Store | Storage | Cost |
|---|---|---|---|---|
| 1 | 100 | 180 | 180 | 1580 |
| 2 | 0 | 0 | 0 | 0 |
Total Cost = $1580
We do not know which of the three scenarios will actually occur next year, but we would like our current purchasing decision to put is in the best position to minimize our expected cost. Bear in mind that by the time we make our second purchasing decision, we will know which of the three scenarios has actually happened.
Formulating a Stochastic Linear Program
Stochastic programs seek to minimize the cost of the first-period decision plus the expected cost of the second-period recourse decision.
\[ \begin{array}{ll}
\min & c^T x + E_{\omega} Q(x,\omega) \\
\mbox{s.t.} & Ax = b \\
& x \geq 0
\end{array}\]
where
\[
\begin{array}{lll}
Q(x,\omega) = & \min & d(\omega)^T y \\
& \mbox{s.t.} & T(\omega)x + W(\omega) y = h(\omega) \\
& & y \geq 0
\end{array} \]
The first linear program minimizes the first-period direct costs, \(c^T x \) plus the expected recourse cost, \(Q(x,\omega) \), over all of the possible scenarios while meeting the first-period constraints, \(Ax = b\).
The recourse cost \(Q\) depends both on \(x\) the first-period decision and on the random event, \(\omega\). The second LP describes how to choose \(y(\omega)\) (a different decision for each random scenario \(\omega\)). It minimizes the cost \(d^Ty\) subject to some recourse function, \(Tx + Wy = h\). This constraint can be thought of as requiring some action to correct the system after the random event occurs. In our example, this constraint would require the purchase of enough gas to supplement the original amount on hand in order to meet the demand.
One important thing to notice in stochastic programs is that the first-period decision, \(x\), is independent of which second-period scenario actually occurs . This is called the nonanticipativity property. The future is uncertain and so today’s decision cannot take advantage of knowledge of the future.
Deterministic Equivalent
The formulation above looks a lot messier than the deterministic LP formulation that we discuss elsewhere. However, we can express this problem in a deterministic form by introducing a different second-period \(y\) variable for each scenario. This formulation is called the deterministic equivalent.
\[ \begin{array}{lllll}
\min & c^Tx + \sum_{i=1}^N p_i d_i^T y_i & & & \\
\mbox{s.t.} & Ax & = & b & \\
& T_i x + W_i y_i & = & h_i & i=1,\ldots,N \\
& x & \geq & 0 & \\
& y_i & \geq & 0 & i=1,\ldots,N
\end{array} \]
where \(N\) is the number of scenarios and \(p_i\) is the probability of the scenario \(i\)’s occurrence.
For our three-scenario problem, we have
\min & c^Tx + p_1 d_1^T y_1 + p_2 d_2^T y_2 + p_3 d_3^T y_3 & & & \\
\mbox{s.t.} & Ax & = & b & \\
& T_1 x + W_1 y_1 & = & h_1 & \\
& T_2 x + W_2 y_2 & = & h_2 & \\
& T_3 x + W_3 y_3 & = & h_3 & \\
& x & \geq & 0 & \\
& y_i & \geq & 0 & i=1,2,3
\end{array}\]
Notice that the nonanticipativity constraint is met. There is only one first-period decision, \(x\), whereas there are \(N\) second-period decisions, one for each scenario. The first-period decision cannot anticipate one scenario over another and must be feasible for each scenario. That is, \(Ax = b\) and \(T_i x + W_i y_i = h_i\) for \(i = 1,…,N\). Because we solve for all the decisions, \(x\) and \(y_i\) simultaneously, we are choosing \(x\) to be (in some sense) optimal over all the scenarios.
Another feature of the deterministic equivalent is worth noting. Because the \(T\) and \(W\) matrices are repeated for every scenario in the model, the size of the problem increases linearly with the number of scenarios. Since the structure of the matrices remains the same and because the constraint matrix has a special shape, solution algorithms can take advantage of these properties. Taking uncertainty into account leads to more robust solutions but also requires more computational effort to obtain the solution.
Strictly speaking, a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can represent the second-stage cost in some closed form. The deterministic equivalent is often called the extensive form.
Comparisons with Other Formulations
Because stochastic programs require more data and computation to solve, most people have opted for simpler solution strategies. One method requires the solution of the problem for each scenario. The solutions to these problems are then examined to find where the solutions are similar and where they are different. Based on this information, subjective decisions can be made to decide the best strategy.
Expected-Value Formulation
A more quantifiable approach is to solve the original LP where all the random data have been replaced with their expected values. Hopefully in this approach we will do alright on average. For our example then, we consider the (expected value) problem data to be
| Year | Gas cost ($) | Demand |
|---|---|---|
| 1 | 5.0 | 100 |
| 2 | 6.167 | 143.33 |
Solving this problem gives the following result:
| Year | Purchase to Use | Purchase to Store | Storage | Cost |
|---|---|---|---|---|
| 1 | 100 | 143.33 | 143.33 | 1360 |
| 2 | 0 | 0 | 0 | 0 |
Cost = $1360.00
Let’s compute what happens in each scenario if we implement the expected value solution:
| Scenario | Recourse Action | Recourse Cost | Total Cost |
|---|---|---|---|
| Normal | Store 43.33 excess @ $1 per unit | 43.33 | 1403.33 |
| Cold | Buy 6.67 units @ $6 per unit | 40 | 1400 |
| Very Cold | Buy 36.67 units @ $7.5 per unit | 275 | 1635 |
The expected total cost over all scenarios is \(\frac{1}{3} 1403.33 + \frac{1}{3} 1400 + \frac{1}{3} 1635 = 1479.44.\)
Stochastic Programming Solution
Forming and solving the stochastic linear program gives the following solution:
| Year | Purchase to Use | Purchase to Store | Storage | Cost |
|---|---|---|---|---|
| 1 Normal | 100 | 100 | 100 | 1100 |
| 2 Normal | 0 | 0 | 0 | 0 |
| 2 Cold | 50 | 0 | 0 | 300 |
| 2 Very Cold | 80 | 0 | 0 | 600 |
Cost = \(1100 + \frac{1}{3}300 + \frac{1}{3} 600 = 1400.\)
Similarly we can compute the costs for the stochastic programming solution for each scenario:
| Scenario | Recourse Action | Recourse Cost | Total Cost |
|---|---|---|---|
| Normal | None | 0 | 1100 |
| Cold | Buy 50 units @ $6 per unit | 300 | 1400 |
| Very Cold | Buy 80 units @ $7.5 per unit | 600 | 1700 |
The expected total cost over all scenarios is \(\frac{1}{3}1100 + \frac{1}{3}1400 + \frac{1}{3}1700= 1400.\)
The difference in these average costs ($79.44) is the value of the stochastic solution over the expected-value solution. Also, notice that the cost of the stochastic solution is greater than or equal to the optimal solution for each scenario solved separately
(\(1100\geq 1000, 1400 \geq 1400, 1635 \geq 1580\)). By solving each scenario alone, one assumes perfect information about the future to obtain a minimum cost. The stochastic solution is minimizing over a number of scenarios and, as a result, sacrifices the minimum cost for each scenario in order to obtain a robust solution over all the scenarios.
Conclusion
Randomness in problem data poses a serious challenge for solving many linear programming problems. The solutions obtained are optimal for the specific problem but may not be optimal for the situation that actually occurs. Being able to take this randomness into account is critical for many problems where the essence of the problem is dealing with the randomness in some optimal way. Stochastic programming enables the modeller to create a solution that is optimal over a set of scenarios.
Links
- Resources
- Test Problems
- A POrtable Stochastic programming Test Set (POSTS) by Derek Holmes and John Birge
- Test-Problem Collection for Stochastic Linear Programming by K. Ariyawansa and Andrew Felt
- Test Set by Jeff Linderoth, Alexander Shapiro and Stephen Wright