In a two-stage or multi-stage stochastic optimisation problem, a scenario recourse inequality (SRI) is a constraint class that allows the second stage to choose its optimal action independently for each possible future scenario, rather than forcing all scenarios to use a single fixed recourse rule. The inequalities then project these scenario-specific optimal actions back onto a first-stage decision (the "present") that remains feasible across every future.
Classical two-stage stochastic linear programming uses the L-shaped method (Benders decomposition) to handle uncertainty. The L-shaped approach computes a single aggregate recourse strategy that is optimal-in-expectation across all scenarios. But the "expected" scenario often never occurs. A route planned for average demand may be terrible under high-demand peaks or low-demand valleys.
Scenario recourse inequalities tighten the dual bound by allowing stage two to respond optimally in each scenario independently. This is more flexible than aggregate recourse, yet still produces a stage-one decision that is robust—it works for all scenarios. The payoff is a stronger relaxation and faster convergence: research shows SRI algorithms solve hundreds more benchmark instances than L-shaped cuts.
A brewery must decide the sequence of 30 delivery stops each morning before customer orders arrive (stage one decision). Once at each stop, it discovers the actual quantity ordered and adjusts the load unloaded from the truck (stage two recourse).
Demand scenarios vary widely. On cold days, winter supply orders spike; on hot days, they crash. A route sequenced for "average" demand might stop at a high-volume location too early, forcing the truck to make extra trips or skip deliveries. A route sequenced for one scenario (cold-day high demand) can be wasteful under another (hot-day low demand).
With L-shaped cuts, the optimiser chooses a single stage-one route that balances all demand scenarios on average. With scenario recourse inequalities, the optimiser instead:
The result is a route that remains invariant but supports optimal adjustment in every future. The brewery can unload more at any stop if demand surprises high, or less if it surprises low—all within the constraints of truck capacity and time windows.
Mathematically, a two-stage stochastic mixed-integer programme is:
min c'x + E[Q(x, ω)]
s.t. Ax ≤ b, x ∈ X
where Q(x, ω) is the optimal second-stage recourse value given first-stage decision x and scenario ω. Classical L-shaped methods approximate the expected recourse with a single piecewise-linear function built from scenario subproblems. Scenario recourse inequalities instead construct the convex hull of the scenario-specific recourse polytopes, yielding tighter cuts that distinguish between robust-in-all-scenarios and average-case decisions.
Scenario Recourse Inequality: A constraint that optimises first-stage decisions to be robust across all scenarios by projecting scenario-optimal second-stage recourse back onto first-stage feasibility.