Theorem 3.2 (corrected: a node runs out when its capacity is no longer positive) — Picard iteration for fulfillment converges in at most |Q_T| + 1 iterations
ProvedPicardFO.Fulfill.theorem_3_2Consider the fulfillment optimization problem with products, nodes, real initial inventories and capacities , a sequence of orders for products , and a feasible policy satisfying Inventory Independence, Consistency and Monotonicity (Assumptions 1–3). Run Algorithm 1 (the Picard iteration) with the time steps partitioned by products: each product is owned by one process, and order is handled by the owner of . Let be the actions of the sequential run and the cache after iteration . Fix a horizon and let
be the set of nodes that run out of capacity in the sequential run. Then:
- for every iteration ,
- whenever the convergence test of Algorithm 1 succeeds at an iteration , that is for all , the returned cache is the sequential action sequence: for all .
The number of Picard iterations needed is thus bounded by one more than the number of nodes that run out of capacity, independently of the horizon and of the number of products and processes. Since each iteration evaluates the policy on orders per process in parallel, this bound is what turns the Picard iteration into a speed-up of policy simulation for fulfillment.
Formalization Note Actions are Option (Fin J) (none is the paper's action ); orders are 0-based (Lean order t < T is the paper's order ); Q … T is the paper's computed over the sequential states (the state after the last order is not included); cache … k is ; processes are an arbitrary type ι with ownership map own. Runs are defined for all orders, and the horizon enters only through Q … T and t < T; no step of Algorithm 1 at order depends on later orders.
Differences from the source:
- correction: 𝒬_T = |{j : τ_j ≤ T}| with τ_j = min{t : c^{seq}{t,j} = 0} → |{j : c{1,j} > 0, c^{seq}_{t,j} ≤ 0 for some t ∈ [T]}|; reason: as printed the theorem is false over the paper's real capacities. Counterexample satisfying every assumption: J = 1, products A, B owned by two processes, x₁ = 3 for both at node 1, c₁ = 3/2, orders A, B, A, π = "node 1 if feasible, else 0": sequential capacities 3/2, 1/2, −1/2 are never 0, so 𝒬_T = 0, but a^{seq} = (1, 1, 0) and α¹ = (1, 1, 1). On integer data the corrected Q_T is contained in the printed one, so the corrected statement implies the printed one there.
- reading: Assumption 2 with j′ arbitrary → j′ ≠ π((x, c), ω); reason: read literally only the never-fulfilling policy satisfies it (a policy choosing j would have to keep choosing j after c_j is set to 0), which makes the theorem vacuous; the chosen reading is the weaker hypothesis.
- reading: Assumption 3's first clause for every decision j → for decisions j ∈ [J]; second clause for every decision including 0; reason: e_{i,0} is undefined.
- reading: "converges in at most 𝒬_T + 1 iterations" → the cache equals a^{seq} on [T] in every iteration k ≥ |Q_T| + 1, and the cache returned by the convergence test is a^{seq}; reason: the sense used in the paper (proof of Proposition 2.1, p. 12, "setting k = T"); the test of line 10 needs one more iteration to observe convergence.
- generalization: M processes and a partition of [I] → any type of processes and any ownership map (processes may own no product); reason: specializes to ι = Fin M and a partition.
- encoding: action set {0} ∪ [J], 1-based orders, finite disturbance sequence {ω_t : t ∈ [T]} → Option (Fin J), 0-based orders, ω : ℕ → Ω with t < T; reason: Lean convention, same instances (later orders never influence earlier steps).
import Mathlib import Definitions.Def_PicardFO_Fulfill_Model
namespace PicardFO.Fulfill
/-- Theorem 3.2 (p. 6), corrected (a node runs out when its capacity is no longer positive):
for a feasible policy satisfying Assumptions 1–3, the cache of Algorithm 1 (partition by
products) equals the sequential actions on the first `T` orders in every iteration
`k ≥ |Q_T| + 1`; and whenever the convergence test of line 10 succeeds at an iteration
`k ≥ 1`, the returned cache is the sequential one. -/
theorem theorem_3_2 {I J : ℕ} {Ω ι : Type*} (prod : Ω → Fin I)
(π : State I J → Ω → Option (Fin J)) (s₁ : State I J) (ω : ℕ → Ω) (own : Fin I → ι)
(hfeas : PolicyFeasible prod π) (h1 : InvIndep prod π) (h2 : Consistent prod π)
(h3 : MonotonePolicy prod π) (T : ℕ) :
(∀ k : ℕ, (Q prod π s₁ ω T).card + 1 ≤ k →
∀ t < T, cache prod π s₁ ω own k t = seqAct prod π s₁ ω t) ∧
(∀ k : ℕ, 1 ≤ k →
(∀ t < T, cache prod π s₁ ω own k t = cache prod π s₁ ω own (k - 1) t) →
∀ t < T, cache prod π s₁ ω own k t = seqAct prod π s₁ ω t) := by sorry
end PicardFO.Fulfill
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.