The value of the stochastic solution in two-stage planning
Replacing uncertain quantities by their averages yields a plan that is optimal only for the average scenario. Stochastic programming measures the cost of this simplification through the value of the stochastic solution, illustrated with a simple inventory problem.
Many planning decisions are taken before the relevant uncertain quantities are known.
A network operator chooses a route before knowing which links will fail. A planner orders stock before knowing demand. A project commits resources before learning which risks will materialise. The common shortcut is to replace every uncertain quantity by its average and optimise as if the future were certain. This approach is simple and widely used, but it produces a plan that is optimal only for the average scenario, which may never occur.
A bakery that bakes before opening faces this problem every morning. If demand averages 100 loaves, the average plan bakes 100. On a busy day customers are turned away and the margin on every missing loaf is lost; on a quiet day the surplus is discarded. When a lost sale costs several times more than a discarded loaf, baking somewhat more than the average is cheaper over a year, even though some bread is wasted on most days. A hospital rostering nurses before admissions are known, or a municipality buying road salt before the winter, faces the same choice.
This article examines the cost of planning with averages and when it is worth modelling the uncertainty explicitly. Stochastic programming quantifies this cost with a single measure.
Two-stage stochastic programming with recourse goes back to Dantzig (1955) and Beale (1955). The value of the stochastic solution (VSS) and the expected value of perfect information (EVPI), and the inequalities that bind them, are standard results presented in Birge and Louveaux's textbook (2011); EVPI itself comes from decision theory (Raiffa and Schlaifer, 1961). When exact solution is too slow, simheuristics, which combine heuristics with Monte Carlo simulation, are reviewed by Juan and colleagues (2015).
Two stages
A two-stage problem separates what must be decided now from what can be repaired later. A first-stage decision is taken before the random outcome is known. Once is observed, a recourse action repairs the plan at some cost. The goal is to minimise the expected total cost:
Three measures: EEV, RP and WS
- EEV: solve the problem with every random quantity replaced by its mean, then evaluate that plan against the real uncertainty.
- RP: the optimum of the stochastic program above.
- WS (wait and see): the expected cost if were known before deciding.
For a minimisation problem these always satisfy
The two differences have names. VSS = EEV − RP is the loss from planning with averages. EVPI = RP − WS is the most a perfect forecast could be worth. A large VSS indicates that the uncertainty should be modelled. A large EVPI indicates that better information is worth acquiring.
Example: network routing
I tested this on a small model of a multi-orbit satellite network: ten nodes, links that fade or drop between epochs, and sixty sampled link-state scenarios. The operator commits one primary route; if a link on it fails, traffic moves to the best available backup at a re-provisioning penalty, or an SLA penalty is paid if nothing is available. The deterministic plan chose the route that is shortest on average; the stochastic program chose one slightly longer on average but far less likely to need recourse. The VSS was 16.9% of the deterministic plan's expected latency.
The same trade-off is familiar to commuters. A motorway that is the fastest route on an average day can be the wrong choice if a single accident adds an hour, and experienced drivers often take a slightly longer road that is rarely blocked. The stochastic program states that judgement in numbers.
Heuristic methods
The stochastic program, solved exactly as a mixed-integer linear program, took about ten seconds; a biased-randomised heuristic with Monte Carlo evaluation (a simheuristic) found the same route in about five milliseconds. One caveat applies: this instance had only fifteen candidate routes, so brute force would also take milliseconds. The case for heuristics is on larger networks, which this small study did not test. Heuristics carry no optimality guarantee, so the good practice is to validate them against exact methods where both run.
The figure below illustrates two results: WS ≤ RP ≤ EEV always holds, and the gap EEV − RP grows with uncertainty and with the cost of recourse.
The figure uses the bakery problem rather than the satellite network: commit units now at €1 each, before demand is known. Demand averages 100 units with an adjustable spread. Running short costs the recourse price per missing unit; leftovers cost the holding price.
- The average plan. With the defaults, the plan built on the average commits 100 units. The best stochastic plan commits more, because running short is far more expensive than holding stock. The VSS readout shows the cost of planning with the average.
- Low uncertainty. Reduce the spread to 5%. All three bars converge and VSS nearly vanishes, because the average is nearly correct when the future is nearly certain.
- Expensive recourse. Raise the shortage cost to €20 with a spread of 60%. VSS grows to a large share of the bill. This is the bakery whose customers go elsewhere when the shelves are empty.
- Alternative plans. Moving the selected plan shows its cost on the curve. No plan achieves a lower cost than RP, by definition.
- The ordering. No setting makes RP exceed EEV or fall below WS.
Why WS ≤ RP ≤ EEV. The average plan is one of the plans RP minimises over, so . For every outcome , for the stochastic optimum ; taking expectations gives .
Averages describe the centre of a distribution, while many costs arise in its tails: a failed link, a stock-out, a missed deadline. When recourse is expensive, a plan optimised for the average scenario performs poorly. The value of the stochastic solution quantifies this in terms a decision maker can use, and EVPI gives an upper bound on the value of a better forecast.
References
- G. B. Dantzig, "Linear programming under uncertainty", Management Science, 1(3-4), 197-206, 1955.
- E. M. L. Beale, "On minimizing a convex function subject to linear inequalities", Journal of the Royal Statistical Society B, 17(2), 173-184, 1955.
- H. Raiffa and R. Schlaifer, Applied Statistical Decision Theory, Harvard University, 1961.
- J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, 2nd ed., Springer, 2011.
- A. A. Juan, J. Faulin, S. E. Grasman, M. Rabe and G. Figueira, "A review of simheuristics: extending metaheuristics to deal with stochastic combinatorial optimization problems", Operations Research Perspectives, 2, 62-72, 2015.