Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The deterministic consolidation policy πcon(m)\pi^{(m)}_{\rm con}πcon(m)​ (Definition 2)

Definition
owmr_consolidation_policy

by Ming Hu · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinventoryinventory-theoryoperations-researchstochastic-control

Fix m≥1m\ge1m≥1 and define, as in (33),

γˉm=133+3257m,gm=γˉm2,ζm=gmgm−1,Bm=2(gm−1),um=3ζm(1+1/m)4(4+ζm/m).\bar\gamma_m=\frac{13}{3}+\frac{32}{57m},\quad g_m=\frac{\bar\gamma_m}2,\quad\zeta_m=\frac{g_m}{g_m-1},\quad B_m=2(g_m-1),\quad u_m=\frac{3\zeta_m(1+1/m)}{4(4+\zeta_m/m)}.γˉ​m​=313​+57m32​,gm​=2γˉ​m​​,ζm​=gm​−1gm​​,Bm​=2(gm​−1),um​=4(4+ζm​/m)3ζm​(1+1/m)​.

Retailer iii plans at setup cost ki=ζmKik_i=\zeta_mK_iki​=ζm​Ki​; write Gi=Ji(ki)G_i=J_i(k_i)Gi​=Ji​(ki​) and Λi=min⁡xFi(x)\Lambda_i=\min_xF_i(x)Λi​=minx​Fi​(x). If Ki>0K_i>0Ki​>0, let w^i=S^i−s^i\hat w_i=\hat S_i-\hat s_iw^i​=S^i​−s^i​ be the width of a canonical optimum at setup cost kik_iki​, and ui=ki/[GiMi(w^i)]u_i=k_i/[G_iM_i(\hat w_i)]ui​=ki​/[Gi​Mi​(w^i​)] its setup-cost share. The consolidation policy πcon(m)\pi^{(m)}_{\rm con}πcon(m)​ follows four rules.

  1. Retailer policies. Retailer iii uses base stock at a minimizer of FiF_iFi​ if Λi+Ki≤BmGi\Lambda_i+K_i\le B_mG_iΛi​+Ki​≤Bm​Gi​ (an immediate retailer). Otherwise it is a batch retailer and uses the best half window of [s^i,S^i][\hat s_i,\hat S_i][s^i​,S^i​] if ui≤umu_i\le u_mui​≤um​, and the full window [s^i,S^i][\hat s_i,\hat S_i][s^i​,S^i​] otherwise.
  2. Requests and allocation. Retailer iii applies its policy to P^i,t=Pi,t+Δi,t+Ri,t\widehat P_{i,t}=P_{i,t}+\Delta_{i,t}+R_{i,t}Pi,t​=Pi,t​+Δi,t​+Ri,t​. Requests join one FIFO queue, and after the supplier order the warehouse allocates its unallocated stock to requests in queue order, the last one possibly in part.
  3. Dispatch. Allocations to immediate retailers are dispatched at once. A request of a batch retailer, of size QQQ, receives at creation an offset ϑ∈(0,1)\vartheta\in(0,1)ϑ∈(0,1) and ships its entire reserve in each period in which its cumulative allocation rises to or past 3Qϑ/43Q\vartheta/43Qϑ/4, or past 3Q(1+ϑ)/43Q(1+\vartheta)/43Q(1+ϑ)/4 when ϑ<1/3\vartheta<1/3ϑ<1/3, or reaches QQQ.
  4. Supplier orders. If K0>0K_0>0K0​>0, the warehouse uses (s^0+a0,S^0+a0)(\hat s_0+a_0,\hat S_0+a_0)(s^0​+a0​,S^0​+a0​), where (s^0,S^0)(\hat s_0,\hat S_0)(s^0​,S^0​) is a canonical optimum attaining J0(gmK0)J_0(g_mK_0)J0​(gm​K0​) and a0=(−s^0)+a_0=(-\hat s_0)^+a0​=(−s^0​)+; if K0=0K_0=0K0​=0, base stock at a nonnegative minimizer of fL0f_{L_0}fL0​​. It applies this policy to Wt+Ot+∑i(Pi,t−Γi)W_t+O_t+\sum_i(P_{i,t}-\Gamma_i)Wt​+Ot​+∑i​(Pi,t​−Γi​), with Γi\Gamma_iΓi​ the selected targets.

Offsets (Appendix C.7). Ordinary requests are indexed j=1,2,…j=1,2,\dotsj=1,2,… in creation order. For request jjj of a batch retailer iii, of size QjQ_jQj​, created in period τj\tau_jτj​, the credited full-lifetime proxy (C.29) is

Zj(ϑ)=Ki[1+Nj(ϑ)]+(h+p)∑t=τjτj+L0(Rj,t(ϑ)−Xt)+,\mathcal Z_j(\vartheta)=K_i[1+N_j(\vartheta)]+(h+p)\sum_{t=\tau_j}^{\tau_j+L_0}(R_{j,t}(\vartheta)-X_t)^+,Zj​(ϑ)=Ki​[1+Nj​(ϑ)]+(h+p)t=τj​∑τj​+L0​​(Rj,t​(ϑ)−Xt​)+,

where Nj(ϑ)N_j(\vartheta)Nj​(ϑ) is the number of interior thresholds, Rj,t(ϑ)R_{j,t}(\vartheta)Rj,t​(ϑ) the stock allocated to request jjj and retained at the warehouse in period ttt, and Xt=∑i(Γi−P^i,t)X_t=\sum_i(\Gamma_i-\widehat P_{i,t})Xt​=∑i​(Γi​−Pi,t​) the total ideal depletion. With zj(ϑ)z_j(\vartheta)zj​(ϑ) its average over the fresh demand vectors of periods τj,…,τj+L0−1\tau_j,\dots,\tau_j+L_0-1τj​,…,τj​+L0​−1 given the state at creation, and zˉj=∫01zj(ϑ) dϑ\bar z_j=\int_0^1z_j(\vartheta)\,d\varthetazˉj​=∫01​zj​(ϑ)dϑ, the offset is the first rational ϑ\varthetaϑ in a fixed enumeration of Q∩(0,1)\mathbb Q\cap(0,1)Q∩(0,1) with zj(ϑ)<zˉj+2−jz_j(\vartheta)<\bar z_j+2^{-j}zj​(ϑ)<zˉj​+2−j (Lemma C.7).

Initialization (Appendix C.8). Prescribed pipelines arrive without new orders, the remaining warehouse stock is sent to a fixed retailer, and no further action is taken until it is received and every retailer net inventory IiI_iIi​ is at most Γi\Gamma_iΓi​. Then retailer iii receives an initial request of size Γi−Ii\Gamma_i-I_iΓi​−Ii​ (if positive), initial requests of batch retailers get fixed offsets, and the four rules run, so the first supplier order raises the supplier position to its shifted target.

Theorem 2 bounds the long-run average cost of this policy for arbitrary nonnegative setup costs.

Formalization Note The choices (canonical optima, best half windows, minimizers, the supplier pair, the fixed retailer, the fixed initial offsets in (0,1)(0,1)(0,1), and the enumeration) are parameters c : ConChoice n, constrained by IsConChoice N m c; GiG_iGi​ and uiu_iui​ are compared in [0,∞][0,\infty][0,∞]. Simultaneous requests are queued and indexed in increasing retailer index. With Tpipe=max⁡(L0,max⁡iLi)T_{\rm pipe}=\max(L_0,\max_iL_i)Tpipe​=max(L0​,maxi​Li​), the stock is sent in period Tpipe−1T_{\rm pipe}-1Tpipe​−1 (period 000 if Tpipe=0T_{\rm pipe}=0Tpipe​=0), after its receipts, and the policy starts in the first later period, no earlier than the arrival of that shipment, in which every Ii≤ΓiI_i\le\Gamma_iIi​≤Γi​ after the receipts. The averages zjz_jzj​ are computed by simulating the ideal dynamics (supplier orders, requests, and allocations, which do not depend on offsets) over the next L0L_0L0​ periods; the value 1/21/21/2 used when no rational satisfies the inequality is a formal default that Lemma C.7 shows is never used. zˉj\bar z_jzˉj​ is a Lebesgue integral over (0,1)(0,1)(0,1) in [0,∞][0,\infty][0,∞].

Definition code
import Definitions.Def_owmr_queue_engine

/-!
# The deterministic consolidation policy `π_con^{(m)}` (Definition 2)

Source: M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse
Multi-Retailer Systems", Section 6 (equation (33) and Definition 2), Appendix C.2
(policy and allocation), Appendix C.7 (deterministic offset selection, Lemma C.7 and the
credited full-lifetime proxy (C.29)), and Appendix C.8 (initialization).

The definition involves choices (canonical optima, minimizing half windows, minimizers, a fixed
retailer for the initialization, fixed offsets of the initial requests, and an enumeration of
the rationals in `(0,1)`). They are collected in `ConChoice`; `IsConChoice` states the properties
Definition 2 requires of them. Simultaneous requests join the queue, and are indexed, in
increasing retailer index (a fixed tie-breaking rule; retailer labels are arbitrary).

Initialization (Appendix C.8): no orders or dispatches until all prescribed pipelines have
arrived (the last can arrive in period `Tpipe - 1`, where `Tpipe = max(L₀, max_i L_i)`; with
truncated subtraction, `Tpipe - 1 = 0` if `Tpipe = 0`); in period `Tpipe - 1`, after its
receipts, the whole warehouse stock is sent to the fixed retailer `sendTo`; no further action
until that shipment has arrived and every retailer net inventory is at most its selected target
`Γ_i = S_i` (checked after the receipts of each period `t > Tpipe - 1`). In the first such period
the policy starts: retailer `i` gets an initial request of size `Γ_i - I_i`
(if positive), the initial requests of batch retailers get the fixed offsets, and the supplier
rule and the queue then run as in Definition 2 (its first order raises the supplier position to
the shifted target).

Offsets of ordinary requests of batch retailers (Appendix C.7): ordinary requests are indexed
`j = 1, 2, …` in creation order. For request `j` (retailer `i`, size `Q_j`, created in period
`τ_j`) and an offset `ϑ`, the credited full-lifetime proxy is
`𝒵_j(ϑ) = K_i (1 + N_j(ϑ)) + (h + p) ∑_{t=τ_j}^{τ_j+L₀} (R_{j,t}(ϑ) - X_t)⁺`, where `N_j(ϑ)` is
the number of interior thresholds (`2` if `ϑ < 1/3`, else `1`), `R_{j,t}(ϑ)` the stock allocated
to request `j` and retained at the warehouse in period `t`, and `X_t` the total ideal depletion
`∑_i (Γ_i - P̂_{i,t})`. It depends on the ideal state at creation and on the fresh demand vectors
of periods `τ_j, …, τ_j + L₀ - 1`. With `z_j(ϑ)` its conditional expectation given the state at
creation and `z̄_j = ∫_0^1 z_j(ϑ) dϑ`, the offset is the first rational `ϑ` in the enumeration with
`z_j(ϑ) < z̄_j + 2^{-j}`.
-/

open MeasureTheory
open scoped ENNReal NNReal

noncomputable section

namespace OWMR

variable {n : ℕ}

/-- `γ̄_m = 13/3 + 32/(57m)` from (33). -/
def conGammaBar (m : ℝ) : ℝ := 13 / 3 + 32 / (57 * m)

/-- `g_m = γ̄_m / 2` from (33). -/
def conG (m : ℝ) : ℝ := conGammaBar m / 2

/-- `ζ_m = g_m / (g_m - 1)` from (33). -/
def conZeta (m : ℝ) : ℝ := conG m / (conG m - 1)

/-- `B_m = 2 (g_m - 1)` from (33). -/
def conB (m : ℝ) : ℝ := 2 * (conG m - 1)

/-- `u_m = 3 ζ_m (1 + 1/m) / (4 (4 + ζ_m/m))` from (33). -/
def conU (m : ℝ) : ℝ := 3 * conZeta m * (1 + 1 / m) / (4 * (4 + conZeta m / m))

/-- The choices made in Definition 2: retailer `(s_i, S_i)` (base stock when `s_i = S_i`) and
batch flags, the supplier `(s₀, S₀)`, the fixed retailer that receives the initial warehouse
stock, the fixed offsets of initial requests, and the enumeration of `ℚ ∩ (0,1)`. -/
structure ConChoice (n : ℕ) where
  s : Fin n → ℝ
  S : Fin n → ℝ
  batch : Fin n → Bool
  s0 : ℝ
  S0 : ℝ
  sendTo : Fin n
  initOffset : Fin n → ℝ
  enum : ℕ ≃ {q : ℚ // 0 < q ∧ q < 1}

/-- The requirements of Definition 2 (with `k_i = ζ_m K_i`, `G_i = J_i(k_i)`,
`Λ_i = min_x F_i(x)`):
* (i) if `Λ_i + K_i ≤ B_m G_i`, retailer `i` is a non-batch (immediate) retailer using base stock
  at a minimizer of `F_i`; otherwise it is a batch retailer and, for a canonical optimum
  `(ŝ_i, Ŝ_i)` at setup cost `k_i` with width `ŵ_i` and setup share
  `u_i = k_i / (G_i M_i(ŵ_i))`, it uses a minimizing half window of `[ŝ_i, Ŝ_i]` if `u_i ≤ u_m`
  and `(ŝ_i, Ŝ_i)` otherwise;
* (iv) if `K₀ > 0`, the supplier uses `(ŝ₀ + a₀, Ŝ₀ + a₀)` for a canonical optimum `(ŝ₀, Ŝ₀)`
  attaining `J₀(g_m K₀)`, with `a₀ = (-ŝ₀)⁺`; if `K₀ = 0`, base stock at a nonnegative minimizer
  of `f_{L₀}`;
* the fixed offsets of initial requests lie in `(0,1)`. -/
def IsConChoice (N : Network n) (m : ℝ) (c : ConChoice n) : Prop :=
  (∀ i,
    (ENNReal.ofReal ((⨅ y, N.F i y) + N.K i)
        ≤ ENNReal.ofReal (conB m) * N.J i (conZeta m * N.K i) →
      c.batch i = false ∧ c.s i = c.S i ∧ ∀ y, N.F i (c.S i) ≤ N.F i y) ∧
    (ENNReal.ofReal (conB m) * N.J i (conZeta m * N.K i)
        < ENNReal.ofReal ((⨅ y, N.F i y) + N.K i) →
      c.batch i = true ∧ ∃ sh Sh : ℝ,
        IsCanonicalOptimum (N.marginal i) (N.F i) (conZeta m * N.K i) sh Sh ∧
        (ENNReal.ofReal (conZeta m * N.K i)
              / (N.J i (conZeta m * N.K i) * renewalM (N.marginal i) (Sh - sh))
            ≤ ENNReal.ofReal (conU m) →
          IsBestHalfWindow (N.marginal i) (N.F i) sh Sh (c.s i) (c.S i)) ∧
        (ENNReal.ofReal (conU m)
            < ENNReal.ofReal (conZeta m * N.K i)
              / (N.J i (conZeta m * N.K i) * renewalM (N.marginal i) (Sh - sh)) →
          c.s i = sh ∧ c.S i = Sh))) ∧
  (0 < N.K0 → ∃ sh Sh : ℝ, IsCanonicalOptimum N.aggregate N.fL0 (conG m * N.K0) sh Sh ∧
    c.s0 = sh + max (-sh) 0 ∧ c.S0 = Sh + max (-sh) 0) ∧
  (N.K0 = 0 → c.s0 = c.S0 ∧ 0 ≤ c.S0 ∧ ∀ y, N.fL0 c.S0 ≤ N.fL0 y) ∧
  (∀ i, 0 < c.initOffset i ∧ c.initOffset i < 1)

/-- The queue parameters of `π_con`: centers `Γ_i = S_i` in the supplier position. -/
def ConChoice.params (c : ConChoice n) : EngParams n where
  s := c.s
  S := c.S
  center := c.S
  batch := c.batch
  s0 := c.s0
  S0 := c.S0

/-! ## Deterministic offset selection (Appendix C.7) -/

/-- Ideal forward simulation from a state `σ` at creation in period `t0` (after the requests and
the supplier order of `t0`), with demand vectors `ds k` in periods `t0 + k`: the state after the
requests and supplier order of period `t0 + k`. Every allocation ships at once here, which does
not change the ideal quantities (positions including outstanding requests, supplier position,
allocations). -/
def idealA (N : Network n) (P : EngParams n) (σ : EngState n) (t0 : ℕ) (ds : ℕ → DemandVec n) :
    ℕ → EngState n
  | 0 => σ
  | k + 1 =>
    (phaseA N.L0 N.L { P with batch := fun _ => false } (fun _ _ _ _ _ => 0) (t0 + k + 1)
      (receive (applyDemand (phaseB N.L { P with batch := fun _ => false } (t0 + k)
        (idealA N P σ t0 ds k)).1 (ds k)) (t0 + k + 1))).1

/-- Cumulative allocation of the request created by retailer `i` in period `t0`, of size `Q`,
after the allocation of period `t0 + k` along the ideal simulation (it is `Q` once the request
has left the queue). -/
def idealAlloc (N : Network n) (P : EngParams n) (σ : EngState n) (t0 : ℕ) (i : Fin n) (Q : ℝ)
    (ds : ℕ → DemandVec n) (k : ℕ) : ℝ :=
  match ((phaseB N.L { P with batch := fun _ => false } (t0 + k)
      (idealA N P σ t0 ds k)).1.queue.find? (fun r => r.born = t0 ∧ r.ret = i)) with
  | some r => r.alloc
  | none => Q

/-- Total ideal depletion `X_{t0+k} = ∑_i (Γ_i - P̂_{i,t0+k})` after the requests of period
`t0 + k`. -/
def idealDepletion (N : Network n) (P : EngParams n) (σ : EngState n) (t0 : ℕ)
    (ds : ℕ → DemandVec n) (k : ℕ) : ℝ :=
  ∑ i, (P.S i - phat N.L (idealA N P σ t0 ds k) (t0 + k) i)

/-- Quantity of a batch request (size `Q`, offset `ϑ`) shipped by the end of period `t0 + k`,
along the allocation path `A k` (cumulative allocation after the allocation of period `t0 + k`;
the allocation before creation is `0`). -/
def shippedPath (Q θ : ℝ) (A : ℕ → ℝ) : ℕ → ℝ
  | 0 => if crossesThreshold Q θ 0 (A 0) then A 0 else 0
  | k + 1 => if crossesThreshold Q θ (A k) (A (k + 1)) then A (k + 1) else shippedPath Q θ A k

/-- The credited full-lifetime proxy (C.29) of request `j` (retailer `i`, size `Q`, created in
period `t0` with state `σ`) for offset `ϑ`, given the demand vectors `ds` of periods
`t0, …, t0 + L₀ - 1`. -/
def proxy (N : Network n) (P : EngParams n) (σ : EngState n) (t0 : ℕ) (i : Fin n) (Q θ : ℝ)
    (ds : ℕ → DemandVec n) : ℝ :=
  N.K i * (1 + if θ < 1 / 3 then 2 else 1)
    + (N.h + N.p) * ∑ k ∈ Finset.range (N.L0 + 1),
      max (idealAlloc N P σ t0 i Q ds k - shippedPath Q θ (idealAlloc N P σ t0 i Q ds) k
        - idealDepletion N P σ t0 ds k) 0

/-- `z_j(ϑ)`: the proxy averaged over the fresh demand vectors of periods
`t0, …, t0 + L₀ - 1`. -/
def proxyMean (N : Network n) (P : EngParams n) (σ : EngState n) (t0 : ℕ) (i : Fin n)
    (Q θ : ℝ) : ℝ≥0∞ :=
  ∫⁻ ds, ENNReal.ofReal (proxy N P σ t0 i Q θ (padHist N.L0 ds))
    ∂(Measure.pi fun _ : Fin N.L0 => N.μ)

open Classical in
/-- The deterministic offset rule of Lemma C.7: the first rational `ϑ ∈ (0,1)` in the enumeration
with `z_j(ϑ) < z̄_j + 2^{-j}`, where `z̄_j = ∫_0^1 z_j(ϑ) dϑ`. (Lemma C.7 shows such a `ϑ` exists;
the value `1/2` is only a formal default.) -/
def conRule (N : Network n) (c : ConChoice n) : OffsetRule n := fun σ t0 j i Q =>
  let z : ℝ → ℝ≥0∞ := fun θ => proxyMean N c.params σ t0 i Q θ
  let zbar : ℝ≥0∞ := ∫⁻ θ in Set.Ioo (0 : ℝ) 1, z θ
  if h : ∃ k : ℕ, z ((c.enum k : ℚ) : ℝ) < zbar + (2 : ℝ≥0∞)⁻¹ ^ j then
    ((c.enum (Nat.find h) : ℚ) : ℝ)
  else 1 / 2

/-! ## The policy -/

/-- One period of `π_con` (including the initialization): returns the state before demand, the
supplier order, and the dispatches. -/
def conStep (N : Network n) (c : ConChoice n) (t : ℕ) (st0 : EngState n) :
    EngState n × ℝ × (Fin n → ℝ) :=
  let st := receive st0 t
  if st.running then runStep N.L0 N.L c.params (conRule N c) t st
  else if t = N.Tpipe - 1 then
    (sendOut N.L t (Pi.single c.sendTo st.Wbar) { st with Wbar := 0 }, 0,
      Pi.single c.sendTo st.Wbar)
  else if N.Tpipe - 1 < t ∧ N.Tpipe - 1 + N.L c.sendTo ≤ t ∧ ∀ i, st.I i ≤ c.S i then
    runStep N.L0 N.L c.params (conRule N c) t
      (startWith st t (fun i => c.S i - st.I i) c.initOffset)
  else (st, 0, 0)

/-- The state of `π_con` at the start of period `t` along the demand sequence `d`. -/
def conRun (N : Network n) (x : InitState n) (c : ConChoice n) (d : ℕ → DemandVec n) :
    ℕ → EngState n
  | 0 => initEngState N x
  | t + 1 => applyDemand (conStep N c t (conRun N x c d t)).1 (d t)

/-- The deterministic consolidation policy `π_con^{(m)}` of Definition 2 (the dependence on `m`
is through the choices `c`, constrained by `IsConChoice N m c`), from the initial state `x`. -/
def conPolicy (N : Network n) (x : InitState n) (c : ConChoice n) : DetPolicy n where
  order t d := (conStep N c t (conRun N x c d t)).2.1
  dispatch t d := (conStep N c t (conRun N x c d t)).2.2

end OWMR
Source
M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse Multi-Retailer Systems", working paper (manuscript of November 2026), Section 6, equation (33) and Definition 2 (p. 27), Appendix C.2 (pp. E.10-E.12), Appendix C.7 with equation (C.29) and Lemma C.7 (p. E.20), and Appendix C.8 (p. E.21).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

This file defines several things for an arbitrary n∈Nn\in\mathbb{N}n∈N (indices i∈[n]={0,1,…,n−1}i\in[n]=\{0,1,\dots,n-1\}i∈[n]={0,1,…,n−1}, with n=0n=0n=0 allowed) and a network NNN:

  • five real functions of a real number mmm;
  • a record type of choices ccc, and a predicate on (N,m,c)(N,m,c)(N,m,c);
  • a forward simulation of an imported state machine, and three quantities read off from it;
  • a proxy cost and its average;
  • an offset rule;
  • a one-period transition and the state sequence it generates;
  • a deterministic policy built from NNN, an initial datum xxx and a choice ccc.

The policy is defined for every choice ccc. Neither the predicate nor mmm enters it.

Conventions

  • y+=max⁡(y,0)y^+=\max(y,0)y+=max(y,0). A real number that is compared or combined with a value in [0,∞][0,\infty][0,∞] is first replaced by y+y^+y+.
  • In [0,∞][0,\infty][0,∞] the order is total, ∞+y=∞\infty+y=\infty∞+y=∞, 0⋅∞=00\cdot\infty=00⋅∞=0, and y/z=y⋅z−1y/z=y\cdot z^{-1}y/z=y⋅z−1 with 0−1=∞0^{-1}=\infty0−1=∞ and ∞−1=0\infty^{-1}=0∞−1=0. Hence y/0=∞y/0=\inftyy/0=∞ for y>0y>0y>0, 0/0=00/0=00/0=0, and y/∞=0y/\infty=0y/∞=0 for finite yyy.
  • Real division by 000 gives 000.
  • The real infimum over y∈Ry\in\mathbb{R}y∈R of a function that is unbounded below gives 000.
  • A real-valued integral gives 000 when its integrand is not integrable. Integrals with values in [0,∞][0,\infty][0,∞] are lower Lebesgue integrals.
  • Subtraction of natural numbers is truncated at 000.
  • ρ⊗k\rho^{\otimes k}ρ⊗k is the kkk-fold product of a probability measure ρ\rhoρ. ρ⊗0\rho^{\otimes 0}ρ⊗0 is the unit mass on the single empty tuple, on which every sum is 000.
  • For a tuple ω=(ω0,…,ωT−1)\omega=(\omega_0,\dots,\omega_{T-1})ω=(ω0​,…,ωT−1​), padT(ω)\mathrm{pad}_T(\omega)padT​(ω) is the sequence equal to ωt\omega_tωt​ for t<Tt<Tt<T and to 000 for t≥Tt\ge Tt≥T.

Imported objects, unfolded

Network data

NNN consists of:

  • L0∈NL_0\in\mathbb{N}L0​∈N, and Li∈NL_i\in\mathbb{N}Li​∈N for each i∈[n]i\in[n]i∈[n];
  • a probability measure μ\muμ on R≥0n\mathbb{R}_{\ge0}^nR≥0n​;
  • reals K0,h,pK_0,h,pK0​,h,p;
  • real vectors (Ki)i∈[n](K_i)_{i\in[n]}(Ki​)i∈[n]​ and (Hi)i∈[n](H_i)_{i\in[n]}(Hi​)i∈[n]​.

Nothing in this file assumes any sign condition on these numbers. The following objects are derived from NNN.

  • ρi\rho_iρi​ is the law of v↦viv\mapsto v_iv↦vi​ under μ\muμ, and ρΣ\rho_\SigmaρΣ​ is the law of v↦∑i∈[n]viv\mapsto\sum_{i\in[n]}v_iv↦∑i∈[n]​vi​ under μ\muμ. Both are probability measures on R≥0\mathbb{R}_{\ge0}R≥0​.
  • Tpipe=max⁡(L0,max⁡i∈[n]Li)T_{\mathrm{pipe}}=\max\big(L_0,\max_{i\in[n]}L_i\big)Tpipe​=max(L0​,maxi∈[n]​Li​), where the inner maximum is 000 when n=0n=0n=0. Also T−=max⁡(Tpipe−1,0)T^-=\max(T_{\mathrm{pipe}}-1,0)T−=max(Tpipe​−1,0), which is the truncated subtraction used in the code.
  • For y∈Ry\in\mathbb{R}y∈R, the functions FiF_iFi​ and fL0f_{L_0}fL0​​ are given below. The sum runs over j=0,…,Lij=0,\dots,L_ij=0,…,Li​ in the first line and over j=0,…,L0−1j=0,\dots,L_0-1j=0,…,L0​−1 in the second.
Fi(y)=∫(Hi(y−∑jzj)++p(∑jzj−y)+) dρi⊗(Li+1)(z),F_i(y)=\int\Big(H_i\big(y-\textstyle\sum_j z_j\big)^++p\big(\textstyle\sum_j z_j-y\big)^+\Big)\,d\rho_i^{\otimes(L_i+1)}(z),Fi​(y)=∫(Hi​(y−∑j​zj​)++p(∑j​zj​−y)+)dρi⊗(Li​+1)​(z), fL0(y)=∫(h(y−∑jzj)++p(∑jzj−y)+) dρΣ⊗L0(z).f_{L_0}(y)=\int\Big(h\big(y-\textstyle\sum_j z_j\big)^++p\big(\textstyle\sum_j z_j-y\big)^+\Big)\,d\rho_\Sigma^{\otimes L_0}(z).fL0​​(y)=∫(h(y−∑j​zj​)++p(∑j​zj​−y)+)dρΣ⊗L0​​(z).

When L0=0L_0=0L0​=0 this gives fL0(y)=h y++p (−y)+f_{L_0}(y)=h\,y^++p\,(-y)^+fL0​​(y)=hy++p(−y)+.

Single-location functionals

Let ρ\rhoρ be a probability measure on R≥0\mathbb{R}_{\ge0}R≥0​, let f:R→Rf:\mathbb{R}\to\mathbb{R}f:R→R, and let K∈RK\in\mathbb{R}K∈R.

Vρ(f,K)∈[0,∞]V_\rho(f,K)\in[0,\infty]Vρ​(f,K)∈[0,∞] (code name slValue). This is the infimum of the quantity displayed below, taken over:

  • all probability spaces (U,U,ν)(U,\mathcal U,\nu)(U,U,ν), and
  • all maps q:N×U×R≥0N→Rq:\mathbb{N}\times U\times\mathbb{R}_{\ge0}^{\mathbb{N}}\to\mathbb{R}q:N×U×R≥0N​→R that are nonnegative, measurable in (u,d)(u,d)(u,d) for each ttt, and nonanticipative, meaning qt(u,d)=qt(u,d′)q_t(u,d)=q_t(u,d')qt​(u,d)=qt​(u,d′) whenever ds=ds′d_s=d'_sds​=ds′​ for all s<ts<ts<t.

In the display, d~=padT(z)\tilde d=\mathrm{pad}_T(z)d~=padT​(z). Write Ji(k)=Vρi(Fi,k)J_i(k)=V_{\rho_i}(F_i,k)Ji​(k)=Vρi​​(Fi​,k).

lim sup⁡T→∞1T∫∑t=0T−1(K 1[qt(u,d~)>0]+f(∑s=0tqs(u,d~)−∑s=0t−1d~s))+ d(ν⊗ρ⊗T)(u,z)\limsup_{T\to\infty}\frac1T\int\sum_{t=0}^{T-1}\Big(K\,\mathbf 1\big[q_t(u,\tilde d)>0\big]+f\Big(\sum_{s=0}^{t}q_s(u,\tilde d)-\sum_{s=0}^{t-1}\tilde d_s\Big)\Big)^+\,d\big(\nu\otimes\rho^{\otimes T}\big)(u,z)T→∞limsup​T1​∫t=0∑T−1​(K1[qt​(u,d~)>0]+f(s=0∑t​qs​(u,d~)−s=0∑t−1​d~s​))+d(ν⊗ρ⊗T)(u,z)

SSρ(f,K;a,A)∈[0,∞]\mathrm{SS}_\rho(f,K;a,A)\in[0,\infty]SSρ​(f,K;a,A)∈[0,∞] (code name ssAvgCost), for reals a,Aa,Aa,A. Given a sequence d~\tilde dd~, set v0=Av_0=Av0​=A. Let vt′=Av'_t=Avt′​=A if vt≤av_t\le avt​≤a and vt′=vtv'_t=v_tvt′​=vt​ otherwise, and let vt+1=vt′−d~tv_{t+1}=v'_t-\tilde d_tvt+1​=vt′​−d~t​. Then:

SSρ(f,K;a,A)=lim sup⁡T→∞1T∫∑t=0T−1(K 1[vt≤a and vt<A]+f(vt′))+ dρ⊗T(z),d~=padT(z).\mathrm{SS}_\rho(f,K;a,A)=\limsup_{T\to\infty}\frac1T\int\sum_{t=0}^{T-1}\Big(K\,\mathbf 1\big[v_t\le a\text{ and }v_t<A\big]+f(v'_t)\Big)^+\,d\rho^{\otimes T}(z),\qquad\tilde d=\mathrm{pad}_T(z).SSρ​(f,K;a,A)=T→∞limsup​T1​∫t=0∑T−1​(K1[vt​≤a and vt​<A]+f(vt′​))+dρ⊗T(z),d~=padT​(z).

COρ(f,K;a,A)\mathrm{CO}_\rho(f,K;a,A)COρ​(f,K;a,A) (code name IsCanonicalOptimum) means all of the following:

  • a<Aa<Aa<A;
  • SSρ(f,K;a,A)=Vρ(f,K)\mathrm{SS}_\rho(f,K;a,A)=V_\rho(f,K)SSρ​(f,K;a,A)=Vρ​(f,K);
  • f(a)+=Vρ(f,K)f(a)^+=V_\rho(f,K)f(a)+=Vρ​(f,K);
  • f(A)+≤Vρ(f,K)f(A)^+\le V_\rho(f,K)f(A)+≤Vρ​(f,K);
  • f(y)+≤Vρ(f,K)f(y)^+\le V_\rho(f,K)f(y)+≤Vρ​(f,K) for all y∈[a,A]y\in[a,A]y∈[a,A].

Because f(a)+f(a)^+f(a)+ is finite, this forces Vρ(f,K)<∞V_\rho(f,K)<\inftyVρ​(f,K)<∞.

BHWρ(f;a^,A^;a,A)\mathrm{BHW}_\rho(f;\hat a,\hat A;a,A)BHWρ​(f;a^,A^;a,A) (code name IsBestHalfWindow) means all of the following:

  • a^≤a<A≤A^\hat a\le a<A\le\hat Aa^≤a<A≤A^;
  • A−a=(A^−a^)/2A-a=(\hat A-\hat a)/2A−a=(A^−a^)/2;
  • SSρ(f,0;a,A)≤SSρ(f,0;a′,A′)\mathrm{SS}_\rho(f,0;a,A)\le\mathrm{SS}_\rho(f,0;a',A')SSρ​(f,0;a,A)≤SSρ​(f,0;a′,A′) for all reals a′,A′a',A'a′,A′ with a^≤a′<A′≤A^\hat a\le a'<A'\le\hat Aa^≤a′<A′≤A^ and A′−a′=(A^−a^)/2A'-a'=(\hat A-\hat a)/2A′−a′=(A^−a^)/2. Both sides use fixed cost 000.

Mρ(w)M_\rho(w)Mρ​(w) (code name renewalM):

Mρ(w)=∑k=0∞ρ⊗k({z∈R≥0k:∑j<kzj<w})∈[0,∞].M_\rho(w)=\sum_{k=0}^{\infty}\rho^{\otimes k}\big(\{z\in\mathbb{R}_{\ge0}^k:\textstyle\sum_{j<k}z_j<w\}\big)\in[0,\infty].Mρ​(w)=k=0∑∞​ρ⊗k({z∈R≥0k​:∑j<k​zj​<w})∈[0,∞].

Its k=0k=0k=0 term is 1[w>0]\mathbf 1[w>0]1[w>0]. So Mρ(w)=0M_\rho(w)=0Mρ​(w)=0 for w≤0w\le0w≤0, and Mρ(w)≥1M_\rho(w)\ge1Mρ​(w)≥1 for w>0w>0w>0.

Engine

Requests, states, parameters and rules.

  • A request rrr has an index retr∈[n]\mathrm{ret}_r\in[n]retr​∈[n], reals sizer\mathrm{size}_rsizer​, allocr\mathrm{alloc}_rallocr​, shippedr\mathrm{shipped}_rshippedr​ and offsetr\mathrm{offset}_roffsetr​, and a birth time bornr∈N\mathrm{born}_r\in\mathbb{N}bornr​∈N.
  • A state σ\sigmaσ has:
    • a flag run\mathrm{run}run, which is true or false;
    • a real Wˉ\bar WWˉ;
    • a vector I∈RnI\in\mathbb{R}^nI∈Rn;
    • real sequences Φ(τ)\Phi(\tau)Φ(τ) and Ψi(τ)\Psi_i(\tau)Ψi​(τ), for i∈[n]i\in[n]i∈[n] and τ∈N\tau\in\mathbb{N}τ∈N (fields supPipe and retPipe);
    • a finite ordered list Q\mathcal QQ of requests, called the queue;
    • a counter nOrd∈N\mathrm{nOrd}\in\mathbb{N}nOrd∈N.
  • Engine parameters are P=(s,S,ctr,β,s0,S0)P=(s,S,\mathrm{ctr},\beta,s_0,S_0)P=(s,S,ctr,β,s0​,S0​), with s,S,ctr∈Rns,S,\mathrm{ctr}\in\mathbb{R}^ns,S,ctr∈Rn, flags β∈{true,false}n\beta\in\{\mathrm{true},\mathrm{false}\}^nβ∈{true,false}n, and s0,S0∈Rs_0,S_0\in\mathbb{R}s0​,S0​∈R.
  • An offset rule is any function R(σ,t,j,i,Q)∈R\mathcal R(\sigma,t,j,i,Q)\in\mathbb{R}R(σ,t,j,i,Q)∈R of a state, two naturals t,jt,jt,j, an index iii and a real QQQ.

Receipt and subtraction.

  • recvt\mathrm{recv}_trecvt​ adds Φ(t)\Phi(t)Φ(t) to Wˉ\bar WWˉ and adds Ψi(t)\Psi_i(t)Ψi​(t) to IiI_iIi​ for each iii. The pipeline entries stay in place.
  • dem(⋅,d)\mathrm{dem}(\cdot,d)dem(⋅,d), for d∈R≥0nd\in\mathbb{R}_{\ge0}^nd∈R≥0n​, subtracts did_idi​ from IiI_iIi​.
  • Neither operation changes anything else.

The quantity p^i\hat p_ip^​i​ (code name phat):

p^i(σ,t)=Ii+∑l=0Li−1Ψi(t+1+l)+∑r∈Q: retr=i(sizer−shippedr).\hat p_i(\sigma,t)=I_i+\sum_{l=0}^{L_i-1}\Psi_i(t+1+l)+\sum_{r\in\mathcal Q:\ \mathrm{ret}_r=i}(\mathrm{size}_r-\mathrm{shipped}_r).p^​i​(σ,t)=Ii​+l=0∑Li​−1​Ψi​(t+1+l)+r∈Q: retr​=i∑​(sizer​−shippedr​).

The code writes the last sum as an unallocated part plus an allocated-but-unshipped part.

Phase A at time ttt, with parameters PPP and rule R\mathcal RR, applied to σ\sigmaσ:

  1. The following are computed from σ\sigmaσ:
    • rqi=Si−p^i(σ,t)\mathrm{rq}_i=S_i-\hat p_i(\sigma,t)rqi​=Si​−p^​i​(σ,t) if p^i(σ,t)≤si\hat p_i(\sigma,t)\le s_ip^​i​(σ,t)≤si​, and rqi=0\mathrm{rq}_i=0rqi​=0 otherwise;
    • rs\mathrm{rs}rs, the list of indices with rqi>0\mathrm{rq}_i>0rqi​>0, in increasing order;
    • pos\mathrm{pos}pos, as displayed below;
    • q0=S0−posq_0=S_0-\mathrm{pos}q0​=S0​−pos if pos≤s0\mathrm{pos}\le s_0pos≤s0​, and q0=0q_0=0q0​=0 otherwise. No sign restriction is applied.
  2. The intermediate state σ♯\sigma^\sharpσ♯ is σ\sigmaσ with three changes:
    • q0q_0q0​ is added to Wˉ\bar WWˉ if L0=0L_0=0L0​=0, or to Φ(t+L0)\Phi(t+L_0)Φ(t+L0​) if L0>0L_0>0L0​>0;
    • for each i∈rsi\in\mathrm{rs}i∈rs in order, a request is appended to Q\mathcal QQ with ret=i\mathrm{ret}=iret=i, size=rqi\mathrm{size}=\mathrm{rq}_isize=rqi​, alloc=shipped=0\mathrm{alloc}=\mathrm{shipped}=0alloc=shipped=0, offset=0\mathrm{offset}=0offset=0 and born=t\mathrm{born}=tborn=t;
    • nOrd\mathrm{nOrd}nOrd is increased by the length of rs\mathrm{rs}rs.
  3. The output is σ♯\sigma^\sharpσ♯ together with the number q0q_0q0​, with one change to σ♯\sigma^\sharpσ♯. The request appended at position k=0,1,…k=0,1,\dotsk=0,1,… of rs\mathrm{rs}rs, with index iii, gets offset R(σ♯,t,nOrd(σ)+k+1,i,rqi)\mathcal R\big(\sigma^\sharp,t,\mathrm{nOrd}(\sigma)+k+1,i,\mathrm{rq}_i\big)R(σ♯,t,nOrd(σ)+k+1,i,rqi​) if βi\beta_iβi​ is true, and offset 000 if βi\beta_iβi​ is false.
pos=Wˉ+∑r∈Q(allocr−shippedr)+∑l=0L0−1Φ(t+1+l)+∑i∈[n](Ii+∑l=0Li−1Ψi(t+1+l)−ctri)\mathrm{pos}=\bar W+\sum_{r\in\mathcal Q}(\mathrm{alloc}_r-\mathrm{shipped}_r)+\sum_{l=0}^{L_0-1}\Phi(t+1+l)+\sum_{i\in[n]}\Big(I_i+\sum_{l=0}^{L_i-1}\Psi_i(t+1+l)-\mathrm{ctr}_i\Big)pos=Wˉ+r∈Q∑​(allocr​−shippedr​)+l=0∑L0​−1​Φ(t+1+l)+i∈[n]∑​(Ii​+l=0∑Li​−1​Ψi​(t+1+l)−ctri​)

Crossing predicate. C(Q,θ;y1,y2)C(Q,\theta;y_1,y_2)C(Q,θ;y1​,y2​) holds if and only if at least one of these holds:

  • y1<34Qθ≤y2y_1<\tfrac34Q\theta\le y_2y1​<43​Qθ≤y2​;
  • θ<13\theta<\tfrac13θ<31​ and y1<34Q(1+θ)≤y2y_1<\tfrac34Q(1+\theta)\le y_2y1​<43​Q(1+θ)≤y2​;
  • y1<Qy_1<Qy1​<Q and y2=Qy_2=Qy2​=Q.

Phase B at time ttt, with parameters PPP, applied to σ\sigmaσ:

  1. Go through Q\mathcal QQ in order, with a running amount W′W'W′ that starts at Wˉ\bar WWˉ. For each request rrr:
    • let Δr=min⁡(sizer−allocr,W′)\Delta_r=\min(\mathrm{size}_r-\mathrm{alloc}_r,W')Δr​=min(sizer​−allocr​,W′);
    • the shipped amount is εr=allocr+Δr−shippedr\varepsilon_r=\mathrm{alloc}_r+\Delta_r-\mathrm{shipped}_rεr​=allocr​+Δr​−shippedr​ if βretr\beta_{\mathrm{ret}_r}βretr​​ is false or C(sizer,offsetr;allocr,allocr+Δr)C(\mathrm{size}_r,\mathrm{offset}_r;\mathrm{alloc}_r,\mathrm{alloc}_r+\Delta_r)C(sizer​,offsetr​;allocr​,allocr​+Δr​) holds, and εr=0\varepsilon_r=0εr​=0 otherwise;
    • then allocr\mathrm{alloc}_rallocr​ increases by Δr\Delta_rΔr​, shippedr\mathrm{shipped}_rshippedr​ increases by εr\varepsilon_rεr​, and W′W'W′ decreases by Δr\Delta_rΔr​.
  2. Let qi=∑r: retr=iεrq_i=\sum_{r:\ \mathrm{ret}_r=i}\varepsilon_rqi​=∑r: retr​=i​εr​.
  3. The new state has Wˉ\bar WWˉ equal to the final W′W'W′. Its queue is the updated requests with shippedr<sizer\mathrm{shipped}_r<\mathrm{size}_rshippedr​<sizer​, in the same order.
  4. Then, for each iii, qiq_iqi​ is added to IiI_iIi​ if Li=0L_i=0Li​=0, and to Ψi(t+Li)\Psi_i(t+L_i)Ψi​(t+Li​) if Li>0L_i>0Li​>0. This last operation is the code's sendOut.
  5. Phase B also returns q=(qi)i∈[n]q=(q_i)_{i\in[n]}q=(qi​)i∈[n]​.

When βretr\beta_{\mathrm{ret}_r}βretr​​ is false, shippedr=allocr\mathrm{shipped}_r=\mathrm{alloc}_rshippedr​=allocr​ after the update.

Other engine operations.

  • runStept(σ)\mathrm{runStep}_t(\sigma)runStept​(σ) runs phase A at ttt, then phase B at ttt on the state phase A returns. It returns the state after phase B, the q0q_0q0​ from phase A, and the qqq from phase B.
  • startWith(σ,t,sz,ϑ)\mathrm{startWith}(\sigma,t,\mathrm{sz},\vartheta)startWith(σ,t,sz,ϑ) sets run\mathrm{run}run to true. For each iii with szi>0\mathrm{sz}_i>0szi​>0, in increasing order, it appends to Q\mathcal QQ a request with ret=i\mathrm{ret}=iret=i, size=szi\mathrm{size}=\mathrm{sz}_isize=szi​, alloc=shipped=0\mathrm{alloc}=\mathrm{shipped}=0alloc=shipped=0, offset=ϑi\mathrm{offset}=\vartheta_ioffset=ϑi​ and born=t\mathrm{born}=tborn=t. It does not change nOrd\mathrm{nOrd}nOrd.
  • An initial datum xxx consists of a real WxW^xWx, a vector Ix∈RnI^x\in\mathbb{R}^nIx∈Rn, and real sequences Φx\Phi^xΦx and Ψix\Psi^x_iΨix​. No validity condition is assumed. The state init(N,x)\mathrm{init}(N,x)init(N,x) has:
    • run\mathrm{run}run false;
    • Wˉ=Wx\bar W=W^xWˉ=Wx and I=IxI=I^xI=Ix;
    • Φ(τ)=Φx(τ)\Phi(\tau)=\Phi^x(\tau)Φ(τ)=Φx(τ) for τ<L0\tau<L_0τ<L0​, and 000 otherwise;
    • Ψi(τ)=Ψix(τ)\Psi_i(\tau)=\Psi^x_i(\tau)Ψi​(τ)=Ψix​(τ) for τ<Li\tau<L_iτ<Li​, and 000 otherwise;
    • an empty queue, and nOrd=0\mathrm{nOrd}=0nOrd=0.
  • Only startWith changes the flag run\mathrm{run}run. recv, dem, phases A and B, and sendOut leave it unchanged.
  • A deterministic policy is a pair of maps order:N×(R≥0n)N→R\mathrm{order}:\mathbb{N}\times(\mathbb{R}_{\ge0}^n)^{\mathbb{N}}\to\mathbb{R}order:N×(R≥0n​)N→R and dispatch:N×(R≥0n)N→Rn\mathrm{dispatch}:\mathbb{N}\times(\mathbb{R}_{\ge0}^n)^{\mathbb{N}}\to\mathbb{R}^ndispatch:N×(R≥0n​)N→Rn.

Declarations

Numeric parameters (conGammaBar, conG, conZeta, conB, conU)

For every real mmm:

γˉ(m)=133+3257m,g(m)=γˉ(m)2,ζ(m)=g(m)g(m)−1,\bar\gamma(m)=\frac{13}{3}+\frac{32}{57m},\qquad g(m)=\frac{\bar\gamma(m)}2,\qquad\zeta(m)=\frac{g(m)}{g(m)-1},γˉ​(m)=313​+57m32​,g(m)=2γˉ​(m)​,ζ(m)=g(m)−1g(m)​, b(m)=2(g(m)−1),u(m)=3 ζ(m) (1+1/m)4 (4+ζ(m)/m).b(m)=2\big(g(m)-1\big),\qquad u(m)=\frac{3\,\zeta(m)\,\big(1+1/m\big)}{4\,\big(4+\zeta(m)/m\big)}.b(m)=2(g(m)−1),u(m)=4(4+ζ(m)/m)3ζ(m)(1+1/m)​.

It follows that g(m)=136+1657mg(m)=\frac{13}6+\frac{16}{57m}g(m)=613​+57m16​ and b(m)=γˉ(m)−2=73+3257mb(m)=\bar\gamma(m)-2=\frac73+\frac{32}{57m}b(m)=γˉ​(m)−2=37​+57m32​ for every mmm, including m=0m=0m=0 under the convention below.

Values at m=1m=1m=1:

  • γˉ(1)=93/19≈4.895\bar\gamma(1)=93/19\approx4.895γˉ​(1)=93/19≈4.895;
  • g(1)=93/38≈2.447g(1)=93/38\approx2.447g(1)=93/38≈2.447;
  • ζ(1)=93/55≈1.691\zeta(1)=93/55\approx1.691ζ(1)=93/55≈1.691;
  • b(1)=55/19≈2.895b(1)=55/19\approx2.895b(1)=55/19≈2.895;
  • u(1)=279/626≈0.4457u(1)=279/626\approx0.4457u(1)=279/626≈0.4457.

For m>0m>0m>0 no denominator vanishes, and g(m)>13/6g(m)>13/6g(m)>13/6, 1<ζ(m)<13/71<\zeta(m)<13/71<ζ(m)<13/7, b(m)>7/3b(m)>7/3b(m)>7/3 and u(m)>0u(m)>0u(m)>0.

Real division by 000 gives 000, so the degenerate cases are:

  • m=0m=0m=0: 32/(57m)32/(57m)32/(57m), 1/m1/m1/m and ζ(m)/m\zeta(m)/mζ(m)/m all equal 000. This gives γˉ(0)=13/3\bar\gamma(0)=13/3γˉ​(0)=13/3, g(0)=13/6g(0)=13/6g(0)=13/6, ζ(0)=13/7\zeta(0)=13/7ζ(0)=13/7, b(0)=7/3b(0)=7/3b(0)=7/3 and u(0)=39/112u(0)=39/112u(0)=39/112.
  • m=−32/133m=-32/133m=−32/133: here g(m)=1g(m)=1g(m)=1, so ζ(m)=0\zeta(m)=0ζ(m)=0, b(m)=0b(m)=0b(m)=0 and u(m)=0u(m)=0u(m)=0.
  • 4+ζ(m)/m=04+\zeta(m)/m=04+ζ(m)/m=0 exactly when 1596m2+1125m+96=01596m^2+1125m+96=01596m2+1125m+96=0, that is, m=(−375±72529)/1064≈−0.0993m=(-375\pm\sqrt{72529})/1064\approx-0.0993m=(−375±72529​)/1064≈−0.0993 or −0.6056-0.6056−0.6056. At these values u(m)=0u(m)=0u(m)=0.

γˉ\bar\gammaγˉ​ is used only through ggg. The functions g,ζ,b,ug,\zeta,b,ug,ζ,b,u are used only in the choice predicate.

Choice record (ConChoice n)

A choice ccc consists of:

  • real vectors s=(si)i∈[n]s=(s_i)_{i\in[n]}s=(si​)i∈[n]​ and S=(Si)i∈[n]S=(S_i)_{i\in[n]}S=(Si​)i∈[n]​;
  • flags β=(βi)i∈[n]\beta=(\beta_i)_{i\in[n]}β=(βi​)i∈[n]​, each true or false (field batch);
  • reals s0s_0s0​ and S0S_0S0​;
  • an index ι∈[n]\iota\in[n]ι∈[n] (field sendTo);
  • a real vector θ0=(θi0)i∈[n]\theta^0=(\theta^0_i)_{i\in[n]}θ0=(θi0​)i∈[n]​ (field initOffset);
  • a bijection e:N→Q∩(0,1)e:\mathbb{N}\to\mathbb{Q}\cap(0,1)e:N→Q∩(0,1) (field enum), stored together with its inverse.

The record imposes no constraint between its fields. Because ι\iotaι must lie in [n][n][n], no choice exists when n=0n=0n=0. So for n=0n=0n=0 the predicate, the offset rule, the step, the run and the policy have no instances, and neither do the declarations that take an index iii.

Engine parameters of a choice (ConChoice.params)

Pc=(s,S,ctr,β,s0,S0)P_c=(s,S,\mathrm{ctr},\beta,s_0,S_0)Pc​=(s,S,ctr,β,s0​,S0​) with ctr=S\mathrm{ctr}=Sctr=S. All entries are copied from ccc, and the center vector used in phase A's pos\mathrm{pos}pos is the vector SSS.

Choice predicate (IsConChoice N m c)

For a network NNN, a real mmm and a choice ccc, the predicate is the conjunction of conditions (1) to (4).

Condition (1). For every i∈[n]i\in[n]i∈[n], define in [0,∞][0,\infty][0,∞]:

Λi=(inf⁡y∈RFi(y)+Ki)+,Ri=b(m)+⋅Ji(ζ(m)Ki).\Lambda_i=\Big(\inf_{y\in\mathbb{R}}F_i(y)+K_i\Big)^+,\qquad R_i=b(m)^+\cdot J_i\big(\zeta(m)K_i\big).Λi​=(y∈Rinf​Fi​(y)+Ki​)+,Ri​=b(m)+⋅Ji​(ζ(m)Ki​).
  • First case, Λi≤Ri\Lambda_i\le R_iΛi​≤Ri​: βi\beta_iβi​ is false, si=Sis_i=S_isi​=Si​, and Fi(Si)≤Fi(y)F_i(S_i)\le F_i(y)Fi​(Si​)≤Fi​(y) for all y∈Ry\in\mathbb{R}y∈R.
  • Second case, Ri<ΛiR_i<\Lambda_iRi​<Λi​: βi\beta_iβi​ is true, and there exist reals s^i,S^i\hat s_i,\hat S_is^i​,S^i​ such that COρi(Fi,ζ(m)Ki;s^i,S^i)\mathrm{CO}_{\rho_i}\big(F_i,\zeta(m)K_i;\hat s_i,\hat S_i\big)COρi​​(Fi​,ζ(m)Ki​;s^i​,S^i​) holds and, with rir_iri​ as displayed below:
    • if ri≤u(m)+r_i\le u(m)^+ri​≤u(m)+, then BHWρi(Fi;s^i,S^i;si,Si)\mathrm{BHW}_{\rho_i}\big(F_i;\hat s_i,\hat S_i;s_i,S_i\big)BHWρi​​(Fi​;s^i​,S^i​;si​,Si​) holds;
    • if u(m)+<riu(m)^+<r_iu(m)+<ri​, then si=s^is_i=\hat s_isi​=s^i​ and Si=S^iS_i=\hat S_iSi​=S^i​.
ri=(ζ(m)Ki)+Ji(ζ(m)Ki)⋅Mρi(S^i−s^i)∈[0,∞]r_i=\frac{\big(\zeta(m)K_i\big)^+}{J_i\big(\zeta(m)K_i\big)\cdot M_{\rho_i}\big(\hat S_i-\hat s_i\big)}\in[0,\infty]ri​=Ji​(ζ(m)Ki​)⋅Mρi​​(S^i​−s^i​)(ζ(m)Ki​)+​∈[0,∞]

How the cases split:

  • [0,∞][0,\infty][0,∞] is totally ordered, so exactly one of the two cases applies to each iii. For the chosen witnesses s^i,S^i\hat s_i,\hat S_is^i​,S^i​, exactly one of the two sub-cases applies. Only one witness pair has to work.
  • Λi\Lambda_iΛi​ is always finite.
  • If b(m)>0b(m)>0b(m)>0 and Ji(ζ(m)Ki)=∞J_i(\zeta(m)K_i)=\inftyJi​(ζ(m)Ki​)=∞, then Ri=∞R_i=\inftyRi​=∞ and the first case applies.
  • If b(m)≤0b(m)\le0b(m)≤0, then Ri=0R_i=0Ri​=0 (even when Ji=∞J_i=\inftyJi​=∞), and the second case applies exactly when Λi>0\Lambda_i>0Λi​>0.

Values of rir_iri​ inside the second case. Here CO\mathrm{CO}CO gives Ji(ζ(m)Ki)=Fi(s^i)+<∞J_i(\zeta(m)K_i)=F_i(\hat s_i)^+<\inftyJi​(ζ(m)Ki​)=Fi​(s^i​)+<∞ and Mρi(S^i−s^i)≥1M_{\rho_i}(\hat S_i-\hat s_i)\ge1Mρi​​(S^i​−s^i​)≥1. Hence:

  • ri=0r_i=0ri​=0 if ζ(m)Ki≤0\zeta(m)K_i\le0ζ(m)Ki​≤0;
  • ri=∞r_i=\inftyri​=∞ if Ji(ζ(m)Ki)=0<ζ(m)KiJ_i(\zeta(m)K_i)=0<\zeta(m)K_iJi​(ζ(m)Ki​)=0<ζ(m)Ki​;
  • ri=0r_i=0ri​=0 if Mρi(S^i−s^i)=∞M_{\rho_i}(\hat S_i-\hat s_i)=\inftyMρi​​(S^i​−s^i​)=∞ and Ji(ζ(m)Ki)>0J_i(\zeta(m)K_i)>0Ji​(ζ(m)Ki​)>0;
  • otherwise rir_iri​ is an ordinary ratio of positive reals.

The infimum in Λi\Lambda_iΛi​ is the real infimum of FiF_iFi​ over R\mathbb{R}R, which is 000 if FiF_iFi​ is unbounded below. Also Fi(y)=0F_i(y)=0Fi​(y)=0 at any yyy where its integrand is not integrable.

Condition (2). If K0>0K_0>0K0​>0, there exist reals s^0,S^0\hat s_0,\hat S_0s^0​,S^0​ such that COρΣ(fL0,g(m)K0;s^0,S^0)\mathrm{CO}_{\rho_\Sigma}\big(f_{L_0},g(m)K_0;\hat s_0,\hat S_0\big)COρΣ​​(fL0​​,g(m)K0​;s^0​,S^0​) holds, s0=s^0+(−s^0)+=max⁡(s^0,0)s_0=\hat s_0+(-\hat s_0)^+=\max(\hat s_0,0)s0​=s^0​+(−s^0​)+=max(s^0​,0), and S0=S^0+(−s^0)+S_0=\hat S_0+(-\hat s_0)^+S0​=S^0​+(−s^0​)+. That is, both are shifted up by (−s^0)+(-\hat s_0)^+(−s^0​)+.

Condition (3). If K0=0K_0=0K0​=0, then s0=S0s_0=S_0s0​=S0​, S0≥0S_0\ge0S0​≥0, and fL0(S0)≤fL0(y)f_{L_0}(S_0)\le f_{L_0}(y)fL0​​(S0​)≤fL0​​(y) for all y∈Ry\in\mathbb{R}y∈R.

Condition (4). 0<θi0<10<\theta^0_i<10<θi0​<1 for every i∈[n]i\in[n]i∈[n].

What is left unconstrained: if K0<0K_0<0K0​<0, nothing constrains s0s_0s0​ and S0S_0S0​. Nothing constrains ι\iotaι or eee.

The predicate fails whenever a required object does not exist:

  • in the first case of (1), if FiF_iFi​ has no global minimizer on R\mathbb{R}R;
  • in the second case of (1), if no canonical-optimum pair meets the applicable sub-case. For instance, there may be no canonical optimum at all, or, when ri≤u(m)+r_i\le u(m)^+ri​≤u(m)+, no best half window;
  • in (2), if no canonical optimum exists;
  • in (3), if fL0f_{L_0}fL0​​ has no nonnegative global minimizer on R\mathbb{R}R.

Ideal forward simulation (idealA N P σ t₀ ds)

The inputs are parameters PPP, a state σ\sigmaσ, a time t0∈Nt_0\in\mathbb{N}t0​∈N, and a sequence ds=(dsk)k∈N\mathrm{ds}=(\mathrm{ds}_k)_{k\in\mathbb{N}}ds=(dsk​)k∈N​ in R≥0n\mathbb{R}_{\ge0}^nR≥0n​. Let P∘P^\circP∘ be PPP with every flag βi\beta_iβi​ set to false, and use the offset rule that is identically 000. Then:

σ0=σ,σk+1=At0+k+1(recvt0+k+1(dem(Bt0+k(σk), dsk))).\sigma_0=\sigma,\qquad\sigma_{k+1}=\mathrm A_{t_0+k+1}\Big(\mathrm{recv}_{t_0+k+1}\big(\mathrm{dem}\big(\mathrm B_{t_0+k}(\sigma_k),\ \mathrm{ds}_k\big)\big)\Big).σ0​=σ,σk+1​=At0​+k+1​(recvt0​+k+1​(dem(Bt0​+k​(σk​), dsk​))).

Here Aτ\mathrm A_\tauAτ​ and Bτ\mathrm B_\tauBτ​ are the states returned by phase A and phase B at time τ\tauτ, with parameters P∘P^\circP∘ and the lead times of NNN.

  • Each step does the following in order: phase B of period t0+kt_0+kt0​+k, subtract dsk\mathrm{ds}_kdsk​, receive at t0+k+1t_0+k+1t0​+k+1, and phase A of period t0+k+1t_0+k+1t0​+k+1.
  • The first operation applied to σ\sigmaσ is phase B of period t0t_0t0​.
  • Because all flags are false, new requests get offset 000 and the rule is never evaluated. Phase B ships every request's entire allocated-but-unshipped amount.
  • The values s,S,ctr,s0,S0s,S,\mathrm{ctr},s_0,S_0s,S,ctr,s0​,S0​ are those of PPP.
  • σk\sigma_kσk​ depends only on ds0,…,dsk−1\mathrm{ds}_0,\dots,\mathrm{ds}_{k-1}ds0​,…,dsk−1​.

Allocation read-off (idealAlloc N P σ t₀ i Q ds k)

Take i∈[n]i\in[n]i∈[n] and Q∈RQ\in\mathbb{R}Q∈R. Apply phase B at time t0+kt_0+kt0​+k, with parameters P∘P^\circP∘, to σk\sigma_kσk​. In the resulting queue every request has shipped=alloc\mathrm{shipped}=\mathrm{alloc}shipped=alloc, and only requests with alloc<size\mathrm{alloc}<\mathrm{size}alloc<size remain. In that queue, take the first request rrr, in queue order, with bornr=t0\mathrm{born}_r=t_0bornr​=t0​ and retr=i\mathrm{ret}_r=iretr​=i.

  • If such an rrr exists, αk=allocr\alpha_k=\mathrm{alloc}_rαk​=allocr​.
  • Otherwise αk=Q\alpha_k=Qαk​=Q.

The fallback QQQ is used whenever no such request remains. For example, none was in σ\sigmaσ, or its allocation has reached its size. Requests created inside the simulation are born at t0+1,t0+2,…t_0+1,t_0+2,\dotst0​+1,t0​+2,…, so only requests already in σ\sigmaσ can be found.

Depletion read-off (idealDepletion N P σ t₀ ds k)

δk=∑i′∈[n](Si′−p^i′(σk,t0+k)).\delta_k=\sum_{i'\in[n]}\Big(S_{i'}-\hat p_{i'}(\sigma_k,t_0+k)\Big).δk​=i′∈[n]∑​(Si′​−p^​i′​(σk​,t0​+k)).
  • This is a sum over all indices, with SSS taken from PPP.
  • It is evaluated on σk\sigma_kσk​, before the phase B of period t0+kt_0+kt0​+k. For k=0k=0k=0 it is evaluated on σ\sigmaσ itself.
  • It does not depend on iii, QQQ or θ\thetaθ.
  • It is 000 when n=0n=0n=0.

Shipped-quantity recursion (shippedPath Q θ α)

For reals Q,θQ,\thetaQ,θ and a real sequence α\alphaα:

η0={α0if C(Q,θ;0,α0),0otherwise,ηk+1={αk+1if C(Q,θ;αk,αk+1),ηkotherwise.\eta_0=\begin{cases}\alpha_0&\text{if }C(Q,\theta;0,\alpha_0),\\0&\text{otherwise,}\end{cases}\qquad\eta_{k+1}=\begin{cases}\alpha_{k+1}&\text{if }C(Q,\theta;\alpha_k,\alpha_{k+1}),\\\eta_k&\text{otherwise.}\end{cases}η0​={α0​0​if C(Q,θ;0,α0​),otherwise,​ηk+1​={αk+1​ηk​​if C(Q,θ;αk​,αk+1​),otherwise.​

Equivalently, ηk=αk′\eta_k=\alpha_{k'}ηk​=αk′​ for the largest k′≤kk'\le kk′≤k at which the crossing predicate holds, comparing against αk′−1\alpha_{k'-1}αk′−1​, or against 000 when k′=0k'=0k′=0. If there is no such k′k'k′, then ηk=0\eta_k=0ηk​=0.

Proxy (proxy N P σ t₀ i Q θ ds)

Π(P,σ,t0,i,Q,θ,ds)=Ki (1+κθ)+(h+p)∑k=0L0(αk−ηk−δk)+,κθ={2if θ<1/3,1if θ≥1/3.\Pi(P,\sigma,t_0,i,Q,\theta,\mathrm{ds})=K_i\,(1+\kappa_\theta)+(h+p)\sum_{k=0}^{L_0}\big(\alpha_k-\eta_k-\delta_k\big)^+,\qquad\kappa_\theta=\begin{cases}2&\text{if }\theta<1/3,\\1&\text{if }\theta\ge1/3.\end{cases}Π(P,σ,t0​,i,Q,θ,ds)=Ki​(1+κθ​)+(h+p)k=0∑L0​​(αk​−ηk​−δk​)+,κθ​={21​if θ<1/3,if θ≥1/3.​

The ingredients are:

  • α\alphaα, the allocation read-off for (P,σ,t0,i,Q,ds)(P,\sigma,t_0,i,Q,\mathrm{ds})(P,σ,t0​,i,Q,ds);
  • η\etaη, the shipped-quantity recursion of (Q,θ,α)(Q,\theta,\alpha)(Q,θ,α);
  • δ\deltaδ, the depletion read-off for (P,σ,t0,ds)(P,\sigma,t_0,\mathrm{ds})(P,σ,t0​,ds).

The first term is 3Ki3K_i3Ki​ if θ<1/3\theta<1/3θ<1/3, and 2Ki2K_i2Ki​ otherwise. Here hhh and ppp are the scalars of NNN. The sum has L0+1L_0+1L0​+1 terms (only k=0k=0k=0 when L0=0L_0=0L0​=0), and it uses only ds0,…,dsL0−1\mathrm{ds}_0,\dots,\mathrm{ds}_{L_0-1}ds0​,…,dsL0​−1​.

Proxy average (proxyMean N P σ t₀ i Q θ)

Z(θ)=∫(R≥0n)L0Π(P,σ,t0,i,Q,θ,padL0(ω))+ dμ⊗L0(ω)∈[0,∞].Z(\theta)=\int_{(\mathbb{R}_{\ge0}^n)^{L_0}}\Pi\big(P,\sigma,t_0,i,Q,\theta,\mathrm{pad}_{L_0}(\omega)\big)^+\,d\mu^{\otimes L_0}(\omega)\in[0,\infty].Z(θ)=∫(R≥0n​)L0​​Π(P,σ,t0​,i,Q,θ,padL0​​(ω))+dμ⊗L0​(ω)∈[0,∞].
  • This is a lower Lebesgue integral over L0L_0L0​ independent draws from μ\muμ. The draws serve as ds0,…,dsL0−1\mathrm{ds}_0,\dots,\mathrm{ds}_{L_0-1}ds0​,…,dsL0​−1​, and the zero padding after them is never read.
  • Negative values of Π\PiΠ count as 000.
  • For L0=0L_0=0L0​=0, Z(θ)Z(\theta)Z(θ) is Π+\Pi^+Π+ evaluated with ds≡0\mathrm{ds}\equiv0ds≡0.

Offset rule (conRule N c)

Given a choice ccc, the rule maps (σ,t0,j,i,Q)(\sigma,t_0,j,i,Q)(σ,t0​,j,i,Q) to a real number as follows. Let z(θ)z(\theta)z(θ) be the proxy average with parameters PcP_cPc​ and these σ,t0,i,Q\sigma,t_0,i,Qσ,t0​,i,Q. Let zˉ\bar zzˉ be its lower Lebesgue integral over the open interval, with respect to Lebesgue measure:

zˉ=∫(0,1)z(θ) dθ∈[0,∞].\bar z=\int_{(0,1)}z(\theta)\,d\theta\in[0,\infty].zˉ=∫(0,1)​z(θ)dθ∈[0,∞].

The comparison, made in [0,∞][0,\infty][0,∞], is:

z(e(k))<zˉ+2−j.z\big(e(k)\big)<\bar z+2^{-j}.z(e(k))<zˉ+2−j.
  • If some k∈Nk\in\mathbb{N}k∈N satisfies it, the rule returns the real number e(k∗)e(k^\ast)e(k∗) for the least such k∗k^\astk∗. This is the first rational in the stored enumeration eee that satisfies the inequality, and it lies in (0,1)(0,1)(0,1).
  • Otherwise the rule returns 1/21/21/2.

The fallback fires exactly when z(θ)≥zˉ+2−jz(\theta)\ge\bar z+2^{-j}z(θ)≥zˉ+2−j for every θ∈Q∩(0,1)\theta\in\mathbb{Q}\cap(0,1)θ∈Q∩(0,1). In particular it fires whenever z(θ)=∞z(\theta)=\inftyz(θ)=∞ for all such θ\thetaθ. If zˉ=∞\bar z=\inftyzˉ=∞, the inequality reads z(e(k))<∞z(e(k))<\inftyz(e(k))<∞.

The rule uses ccc only through PcP_cPc​ and eee. It does not involve mmm, ι\iotaι or θ0\theta^0θ0.

In the step below, the rule is evaluated only inside phase A, and only for indices with βi\beta_iβi​ true. Its arguments there are:

  • the intermediate state σ♯\sigma^\sharpσ♯ of that phase A, which already contains the period's q0q_0q0​ and all of the period's new requests with offset 000;
  • t0t_0t0​ equal to the current time;
  • jjj equal to the counter nOrd\mathrm{nOrd}nOrd before that phase A, plus the position of iii in rs\mathrm{rs}rs (counted from 000), plus 111;
  • the index iii;
  • Q=rqiQ=\mathrm{rq}_iQ=rqi​.

Per-period step (conStep N c t ξ)

For a time ttt and a state ξ\xiξ, let ξ′=recvt(ξ)\xi'=\mathrm{recv}_t(\xi)ξ′=recvt​(ξ). The step returns a triple: a state, an order quantity in R\mathbb{R}R, and a dispatch vector in Rn\mathbb{R}^nRn. The first of these branches that applies is used:

  1. Running. If run(ξ′)\mathrm{run}(\xi')run(ξ′) is true, the step returns runStept(ξ′)\mathrm{runStep}_t(\xi')runStept​(ξ′), with parameters PcP_cPc​ and the offset rule above.
  2. Send-out period. Otherwise, if t=T−t=T^-t=T−:
    • The state is ξ′\xi'ξ′ with Wˉ\bar WWˉ set to 000, after which the amount Wˉ(ξ′)\bar W(\xi')Wˉ(ξ′) is sent to index ι\iotaι. It is added to IιI_\iotaIι​ if Lι=0L_\iota=0Lι​=0, and to Ψι(t+Lι)\Psi_\iota(t+L_\iota)Ψι​(t+Lι​) otherwise.
    • The order quantity is 000.
    • The dispatch vector has Wˉ(ξ′)\bar W(\xi')Wˉ(ξ′) in coordinate ι\iotaι and 000 elsewhere.
    • The flag stays false. Note that t=T−t=T^-t=T− means t=0t=0t=0 when Tpipe≤1T_{\mathrm{pipe}}\le1Tpipe​≤1.
  3. Start-up. Otherwise, if t>T−t>T^-t>T−, t≥T−+Lιt\ge T^-+L_\iotat≥T−+Lι​, and Ii(ξ′)≤SiI_i(\xi')\le S_iIi​(ξ′)≤Si​ for every i∈[n]i\in[n]i∈[n]:
    • The step returns runStept\mathrm{runStep}_trunStept​, with parameters PcP_cPc​ and the rule above, applied to startWith(ξ′,t,(Si−Ii(ξ′))i,θ0)\mathrm{startWith}\big(\xi',t,(S_i-I_i(\xi'))_{i},\theta^0\big)startWith(ξ′,t,(Si​−Ii​(ξ′))i​,θ0).
    • So the flag becomes true. For each iii with Ii(ξ′)<SiI_i(\xi')<S_iIi​(ξ′)<Si​, whatever βi\beta_iβi​ is, a request is appended before that period's phases A and B. It has size Si−Ii(ξ′)S_i-I_i(\xi')Si​−Ii​(ξ′), allocation and shipped amount 000, offset θi0\theta^0_iθi0​ and birth time ttt.
    • The two time conditions together say t≥T−+max⁡(Lι,1)t\ge T^-+\max(L_\iota,1)t≥T−+max(Lι​,1).
  4. Idle. Otherwise the step returns (ξ′,0,0)(\xi',0,0)(ξ′,0,0).

No sign restriction is applied to the returned order or dispatch quantities.

Run (conRun N x c d)

For an initial datum xxx and a sequence d=(dt)t∈Nd=(d_t)_{t\in\mathbb{N}}d=(dt​)t∈N​ in R≥0n\mathbb{R}_{\ge0}^nR≥0n​:

X0=init(N,x),Xt+1=dem(state returned by the step at time t from Xt, dt).X_0=\mathrm{init}(N,x),\qquad X_{t+1}=\mathrm{dem}\big(\text{state returned by the step at time }t\text{ from }X_t,\ d_t\big).X0​=init(N,x),Xt+1​=dem(state returned by the step at time t from Xt​, dt​).

XtX_tXt​ depends only on d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​.

Starting from init(N,x)\mathrm{init}(N,x)init(N,x), which has flag false and an empty queue, the flag stays false and the queue stays empty until branch 3 fires. The branches occur in this order:

  • branch 4 for t<T−t<T^-t<T−;
  • branch 2 exactly once, at t=T−t=T^-t=T−;
  • branch 4 again for t>T−t>T^-t>T−, until the first ttt that meets branch 3's conditions;
  • branch 3 at that period;
  • branch 1 at every later period.

If branch 3's conditions are never met, every period after T−T^-T− has order 000 and dispatch 000.

Policy (conPolicy N x c)

This is the deterministic policy with

order(t,d)=order quantity of the step at time t from Xt(d),dispatch(t,d)=dispatch vector of the step at time t from Xt(d),\mathrm{order}(t,d)=\text{order quantity of the step at time }t\text{ from }X_t(d),\qquad\mathrm{dispatch}(t,d)=\text{dispatch vector of the step at time }t\text{ from }X_t(d),order(t,d)=order quantity of the step at time t from Xt​(d),dispatch(t,d)=dispatch vector of the step at time t from Xt​(d),

where Xt(d)X_t(d)Xt​(d) is the run above. By branch, these outputs are:

  • branches 1 and 3: phase A's q0q_0q0​ and phase B's vector qqq;
  • branch 2: order 000, and dispatch Wˉ(ξ′)\bar W(\xi')Wˉ(ξ′) in coordinate ι\iotaι;
  • branch 4: both 000.

At time ttt, both outputs depend on ddd only through d0,…,dt−1d_0,\dots,d_{t-1}d0​,…,dt−1​.

The policy is defined for every choice ccc, whether or not the choice predicate holds, and it does not involve mmm. It uses s,S,β,s0,S0s,S,\beta,s_0,S_0s,S,β,s0​,S0​ (through PcP_cPc​), together with ι\iotaι, θ0\theta^0θ0 and eee.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me