Cut sets of the nested L-shaped method

Definition

StochasticProg_MultistageV2_Cuts

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

A state of the nested L-shaped method assigns to every node $k$ a finite set of feasibility cuts $(D,d)$ , representing constraints (1.3) $Dx_k\ge d$ , and a finite set of optimality cuts $(E,e)$ , representing constraints (1.4) $Ex_k+\theta_k\ge e$ . While node $k$ has no optimality cut its subproblem carries the Step 0 constraint $\theta_k=0$ .

Definition code

import Mathlib
import Definitions.Def_StochasticProg_Multistage_Tree

namespace StochasticProg.MultistageV2

/-- The state of the nested L-shaped method (p. 267): the cuts currently present in every
subproblem NLDS(t,k). A feasibility cut `(D, d) ∈ feas k` is constraint (1.3)
`D x^t_k ≥ d`; an optimality cut `(E, e) ∈ opt k` is constraint (1.4) `E x^t_k + θ^t_k ≥ e`.
While `opt k = ∅` the subproblem carries Step 0's constraint `θ^t_k = 0` (p. 267); Step 2
removes it together with adding the first optimality cut (p. 268). -/
structure Cuts {H : ℕ} (T : Multistage.Tree H) (n : ℕ) where
  /-- feasibility cuts (1.3) of each node -/
  feas : T.Node → Finset ((Fin n → ℝ) × ℝ)
  /-- optimality cuts (1.4) of each node -/
  opt : T.Node → Finset ((Fin n → ℝ) × ℝ)

end StochasticProg.MultistageV2

Source

Birge & Louveaux, Introduction to Stochastic Programming, 2nd ed. (2011), Ch. 6, §6.1, constraints (1.3)–(1.4), Steps 0 and 2, pp. 267–268 (PDF pp. 288–289)

View graph