Theorem 3 — Lagrangian cuts from the local-copy reformulation are valid and tight at binary states

Let $n$ be a node of the scenario tree in the backward step of iteration $i$ of SND/SDDiP, with nodal constraint set $X_n$ (nonempty, compact, mixed integer polyhedral), linear objective $f_n$, lower bound $L_n$, children $m$ with probabilities $q_{nm} \ge 0$ and children's cuts $(v^\ell_m, \pi^\ell_m)$, $\ell = 1,\dots,i$, and assume $X''_n \ne \emptyset$. Let $\hat x \in \{0,1\}^d$ be the binary forward-step state of the parent, let $\hat\pi$ be an optimal solution of the Lagrangian dual (4.3)

and let $\hat v = \mathcal L^i_n(\hat\pi)$. Then the Lagrangian cut $(\hat v, \hat\pi)$ is

1. tight (3.5): $\hat v + \hat\pi^\top\hat x = \underline Q^i_n(\hat x, \psi^{i+1}_n)$, the (attained) optimal value of the updated forward problem (3.1);
2. valid (3.4): if the children's cuts are valid for their true value functions $Q_m$, i.e. $Q_m(x) \ge v^\ell_m + (\pi^\ell_m)^\top x$ for all $m$, $\ell$ and $x \in \{0,1\}^d$, and $\mathcal Q_n = \sum_m q_{nm}Q_m \ge L_n$ on $\{0,1\}^d$, then

where $Q_n$ is the true value function (2.3) of the node.

This is the main result of §4.3: Lagrangian cuts obtained by dualizing the copy constraint $z_n = x_{a(n)}$ of the reformulation (2.1) satisfy the validity and tightness conditions of Definition 2, so SND and SDDiP with these cuts (made finite by choosing basic dual solutions) converge to an optimal solution of a multistage stochastic integer program with binary states.

Formalization Note The paper states Theorem 3 for the whole collection $\{(v^i_n,\pi^i_n)\}_{n\in\Omega^i}$ and proves validity by induction over the stages. The Lean statement is the node statement that carries out both the base case and the induction step: the validity hypotheses on the children are the induction hypothesis, and at a last-stage node (no children, $L_n = 0$) they hold trivially. The paper's sentence follows by applying it at every sampled node, from the last stage backwards. "$Q_n(x_a) \ge \dots$" is stated over all feasible points of (2.3) (the minimum is $+\infty$ when there are none). The hypothesis $X''_n \ne \emptyset$ makes $\mathcal L^i_n$ a genuine minimum, as the paper writes it.