Robust and Stochastic Optimization

So far we have assumed that values such as costs, demand, and production capacity are known. In reality, though, future values are hard to know exactly. Producing more next month can meet demand and raise sales, but if actual demand is low, inventory and costs pile up. Conversely, if you produce too little, you cannot supply when demand surges. Under uncertainty like this, solving for the optimum with a single expected value is not enough.

Suppose one unit sells for 100 and costs 60 to produce, and each unsold unit costs 10 to dispose of. If demand is expected to be 100 units, producing 100 seems reasonable, but actual demand can differ.

No production level guarantees the best result in every situation. So we need to weigh the following questions together.

Robust and stochastic optimization start from the same payoff table. The profit for production level x and demand D is:

You earn revenue on what is sold, pay costs on what is produced, and pay disposal costs on leftover inventory. Missing demand effectively means losing the sales margin (40) on each missed unit. If demand is 80, 100, or 120 units with probabilities 0.2, 0.5, and 0.3, expected demand is 80(0.2) + 100(0.5) + 120(0.3) = 102 units.

For example, if you produce 100 and demand is 80, profit is revenue of 8,000 minus production cost of 6,000 and the disposal cost of 200 for the 20 leftover units, or 1,800. If you leave out sales revenue and compare costs only, the shortage loss (40 per unit) is smaller than the production cost (60 per unit), which leads to the wrong conclusion that producing nothing at all looks cheapest (expected cost 4,080). When comparing, revenue, costs, and opportunity losses must be defined on one consistent basis.

Suppose we know demand is between 80 and 120 units but do not know the probability of each level. Robust optimization treats the uncertain value ξ as varying within an uncertainty set 𝒰, and looks for the decision that performs well even in the worst situation in that set.

The inner part finds the most unfavorable situation within the uncertainty range, and the outer part picks the best decision even in that worst situation. Comparing the worst-case profits in the table above selects 80 units (3,200), because if you produce 80, all 80 sell whatever demand turns out to be. Even if, as with the red line in Figure 1, demand can be anywhere between 80 and 120, the worst case is demand of 80, so the conclusion is the same.

Robust optimization does not always look only at the worst outcome. Minimax regret uses as its criterion how much you would regret a decision compared with the best decision in each situation.

Under this criterion, 100 units (1,400), with the smallest maximum regret, is selected. So the robust solution depends on how you set the uncertainty range and the criterion, and including even very unlikely situations in the range leads to decisions that are more conservative than necessary. Robust optimization is useful when the probability distribution is hard to know, when safety and supply stability matter, or when stepping outside a certain range causes large losses (power supply, inventory management, production planning, supply chain design).

If you know the probabilities, you can maximize expected profit: the results for each scenario multiplied by their probabilities and summed. In the table, expected profit is 3,200 for 80 units, 3,560 for 100, and 2,820 for 120, so 100 units is highest. Even varying output one unit at a time, as in the bold line in Figure 1, the maximum is at 100. Expected demand being 102 does not make producing 102 the best choice.

This result can also be explained by the critical ratio of the newsvendor problem. The loss from making one unit too few is the sales margin of 40, and the loss from making one unit too many is the production and disposal cost of 70. The optimal output is the smallest level at which the probability that demand is at most that level is 40 / (40 + 70) = 0.36 or more; since P(D ≤ 80) = 0.2 and P(D ≤ 100) = 0.7, it is 100 units. If the cost structure or probabilities change, the optimal output changes too.

If you know only the range of demand and not the probabilities, consider robust optimization; if you can estimate the probability of each demand level from past data, consider stochastic optimization. The two approaches are not mutually exclusive: you can build models that use a probability distribution while keeping certain constraints robust, or that weigh expected cost and worst-case loss together.

Instead of only maximizing expected profit, you can also manage the probability of meeting a particular condition. The expression above means: plan so that the probability of meeting demand is at least 95%.

In Figure 2, producing 100 meets demand with a probability of only 70%, so to satisfy the 95% condition you have to produce 120. In exchange, expected profit falls by 740, from 3,560 to 2,820. Showing the cost of maintaining a service level in numbers like this gives a basis for setting the target level. Using chance constraints requires the distribution of demand or information to estimate it, and if the probability estimates themselves are uncertain, that has to be taken into account too.

There are also cases where the expected value alone is not enough. Producing 100 has the highest expected profit, but with 20% probability profit is only 1,800, while producing 80 has an expected profit 360 lower but always yields 3,200. If the variability of outcomes matters, look at risk measures such as variance, probability of loss, worst-case loss, and conditional value at risk (CVaR) as well. When designing a stochastic optimization, first decide whether to optimize average performance or also limit the risk of loss.

If it is hard to express the uncertainty precisely with a single probability distribution, build scenarios such as low demand (0.2), normal demand (0.5), and high demand (0.3). The probabilities may be assumptions made for the analysis or values estimated from past data or forecasting models, so you need to record how they were set in order to interpret the results correctly.

In some problems, not every decision is made at once. Suppose that in stage 1 you set a base output before demand is known, and in stage 2, after seeing actual demand, you can fill any shortfall with rush production at 80 per unit.

A base output of 100 is still optimal, but expected profit rises by 120 to 3,680, and the disadvantage of producing 80 shrinks considerably. This means that having a way to respond later lets you make the initial decision less conservatively. Separating decisions made before the uncertainty is revealed from the responses made after it lets you build a plan that prepares in advance while still responding flexibly.

• Robust optimization: looks for decisions that hold up even in unfavorable situations within the uncertainty range, using the worst case or maximum regret as the criterion.
• Stochastic optimization: optimizes expected performance using the probability of each scenario. Producing to expected demand is not automatically optimal.
• Model definition: if revenue, costs, and opportunity losses are not defined consistently, you get nonsensical solutions.
• Chance constraints · risk: manage service levels or risk of loss as constraints, and show their price as the drop in expected performance.
• Two-stage decisions: if you can respond after the uncertainty is revealed, build that flexibility into the model as well.

Wrapping up the nine optimization topics

The optimization part started from expressing a problem as an objective function and constraints, and went on in turn to methods for solving linear, integer, and nonlinear problems, the effect of constraints and multiple goals on the solution, and finally uncertainty in the inputs. The heart of optimization is not the calculation of the largest or smallest value itself, but expressing real-world goals and constraints properly and finding decisions that can actually be used, with the assumptions and uncertainties made explicit.

This concludes 15 Optimization theory.