Two-stage stochastic programmes make first-stage decisions before uncertainty is revealed, then adapt with recourse decisions after. In most frameworks, recourse decisions are made optimally after each scenario occurs — but the form of the recourse policy (how to respond in each scenario) is implicit, derived from whatever heuristic makes stage-1 decisions. Scenario Recourse Inequalities (SRIs) make the recourse policy itself an explicit decision variable in the stage-1 problem.
The key insight: for each scenario, the optimal recourse decisions follow a specific pattern (e.g., "reload at depot before customer 4" or "skip customer 6"). SRIs encode these patterns as valid cutting planes in the MIP. By adding these cuts, the stage-1 decision-maker simultaneously optimises the initial decisions and commits to the best recourse response for each scenario. This produces an exact algorithm with provable optimality certificates derived from empirical demand distributions.
Stage 1: Plan a delivery route visiting 5 customers (customer set {1,2,3,4,5}) with a vehicle of capacity V. The route is fixed before learning customer demand.
Stochastic scenarios: Three demand scenarios with probabilities: Scenario A (low): customers 1,2,3 demand 10 units each (total 30, fits in V=100). Scenario B (medium): customers 1–4 demand 20 units each (80 total). Scenario C (high): all 5 customers demand 20 units each (100 total).
Without SRIs: Plan a route; hope it works in all scenarios. If Scenario C occurs and actual demand is 100 units, a recourse action (reload at depot) is needed post-hoc — but stage-1 route planning did not anticipate which customers trigger reloads.
With SRIs: Stage-1 optimisation includes integer variables encoding the recourse policy: "in Scenario C, reload before customer 4." SRI cuts enforce that once route order is set, the reload position is a function of the scenario. The MIP solves stage-1 decisions and recourse commitment together, producing a route and a recourse playbook with a provably optimal expected cost and a certificate: "this solution is within 2% of optimal."
Benders decomposition generates cuts from LP dual information about constraint violations. Cuts encode: "if you choose master variables x, subproblem costs at least C(x)."
Scenario Recourse Inequalities are integer valid inequalities specifically structured around the recourse policy decision. They encode: "if demand in scenario s is d_s, and you commit to route r, you must execute recourse action p_s(r)." SRIs are higher-dimensional (they reference both scenario and recourse choice) and are tailored to VRP-like problems where discrete recourse choices matter.
The advantage of SRIs is that they explicitly model the recourse decision, making the stage-1 solution account for scenario-optimal response. Standard stochastic decomposition (scenario-indexed subproblems + Benders cuts) leaves the recourse response implicit, often suboptimal. SRIs close this gap for problems where recourse is discrete and scenario-dependent.
Standard heuristic recourse policies are fast but carry no optimality certificate. Scenario recourse inequalities provide the exact integer formulation that proves optimality under scenario-optimal recourse — replacing a heuristic assumption with a provable guarantee.