Robust capacitated sourcing with volume flexibility: LP (4), base stocks, shifting need and the LPS order
DefinitionRobustVolumeFlex_ModelThe robust rolling-horizon model of capacitated sourcing with volume flexibility, as solved in one decision period .
The planning horizon is indexed by , with the current period. The data are:
- holding cost , backorder penalty , contracted unit cost and flexibility premium ;
- the starting net inventory ;
- base capacities ;
- a demand uncertainty set .
The worst-case cumulative demands are
A triple is feasible for the linear program (4) if, for all :
- ;
- ;
- ;
- and .
It is robustly optimal if it is feasible and minimizes over all feasible triples.
The uncapacitated system has cumulative base stock
Its orders are and in every period with , and in the remaining final periods. The shifting need with lookahead is
The Lookahead Peak-Shaving order is
These are the shared definitions for every statement drawn from the paper.
Formalization Note are real infima/suprema, so theorems using them assume nonempty and bounded. The positive part in is a fold of starting at . Boundary cases of the policy go to the later case, where the order is continuous. In eq. (6) the published end-of-horizon index ranges are inconsistent; here ordering stops in exactly the periods where one unit costs more than backlogging it to the horizon end, .
import Mathlib
/-!
# Robust capacitated sourcing with volume flexibility — the model
J. Gijsbrechts, C. Imdahl, R. N. Boute, J. A. Van Mieghem (2023),
"Optimal robust inventory management with volume flexibility: Matching capacity and demand
with the lookahead peak-shaving policy", *Production and Operations Management*,
https://doi.org/10.1111/poms.14069.
One period `t` of the rolling-horizon robust model of Section 3.2. The planning horizon
`ℕ_t^{t+H-1}` is indexed by `Fin H`, where index `0` is the current period `t` and index `n`
is period `t + n`.
-/
namespace RobustVolumeFlex
open Finset
/-- Data of the robust problem solved in one period (Sections 3.1–3.2):
holding cost `h`, backorder penalty `b`, contracted unit sourcing cost `c`,
flexibility (overtime) premium `cp`, starting net inventory `x = x_{t-1}`,
base capacities `k n = k_{t+n}` and the demand uncertainty set `Ω = Ω_t ⊆ ℝ^H`. -/
structure Params (H : ℕ) where
h : ℝ
b : ℝ
c : ℝ
cp : ℝ
x : ℝ
k : Fin H → ℝ
Ω : Set (Fin H → ℝ)
variable {H : ℕ}
/-- Partial sum `∑_{i=t}^{t+n} v_i` of a vector over the planning horizon. -/
def cumSum (v : Fin H → ℝ) (n : ℕ) : ℝ :=
∑ i ∈ univ.filter (fun i : Fin H => i.val ≤ n), v i
/-- Minimum cumulative demand `D̲_{t+n} = min_{d ∈ Ω} ∑_{i=t}^{t+n} d_i` (eq. (3)). -/
noncomputable def minCumDemand (P : Params H) (n : ℕ) : ℝ :=
sInf ((fun d => cumSum d n) '' P.Ω)
/-- Maximum cumulative demand `D̄_{t+n} = max_{d ∈ Ω} ∑_{i=t}^{t+n} d_i` (eq. (3)). -/
noncomputable def maxCumDemand (P : Params H) (n : ℕ) : ℝ :=
sSup ((fun d => cumSum d n) '' P.Ω)
/-- Feasibility for the linear program (4): order quantities `q`, worst-case inventory
mismatch costs `y` and premium sourcing costs `z` satisfying the constraint sets
`𝓗` (holding), `𝓑` (backlog), `𝓕` (flexibility) and the sign constraints. -/
def IsFeasible (P : Params H) (q y z : Fin H → ℝ) : Prop :=
(∀ n : Fin H, P.h * (P.x + cumSum q n - minCumDemand P n) ≤ y n) ∧
(∀ n : Fin H, -P.b * (P.x + cumSum q n - maxCumDemand P n) ≤ y n) ∧
(∀ n : Fin H, P.cp * (q n - P.k n) ≤ z n) ∧
(∀ n : Fin H, 0 ≤ z n) ∧
(∀ n : Fin H, 0 ≤ q n)
/-- The robust objective of (4): `∑_n (c q_n + y_n + z_n)`. -/
def objective (P : Params H) (q y z : Fin H → ℝ) : ℝ :=
∑ n : Fin H, (P.c * q n + y n + z n)
/-- `(q, y, z)` is an optimal solution of the linear program (4). -/
def IsRobustlyOptimal (P : Params H) (q y z : Fin H → ℝ) : Prop :=
IsFeasible P q y z ∧
∀ q' y' z' : Fin H → ℝ, IsFeasible P q' y' z' → objective P q y z ≤ objective P q' y' z'
/-- Cumulative base-stock level of the uncapacitated system,
`Ŝ_{t+n} = max((b D̄_{t+n} + h D̲_{t+n}) / (b + h), x_{t-1})` (eq. (7)). -/
noncomputable def baseStock (P : Params H) (n : ℕ) : ℝ :=
max ((P.b * maxCumDemand P n + P.h * minCumDemand P n) / (P.b + P.h)) P.x
/-- Optimal order quantities `q̂_{t+n}` of the uncapacitated system (eq. (6)): in period
`t + n` the cumulative order is raised to `Ŝ_{t+n} - x_{t-1}` as long as ordering one unit
there is not more expensive than backlogging it until the end of the planning horizon,
i.e. `c ≤ b · (H - n)`; in the remaining final periods (the last `u` periods, where
`u b < c ≤ (u + 1) b`) nothing is ordered. -/
noncomputable def uncapOrder (P : Params H) (n : Fin H) : ℝ :=
if P.c ≤ P.b * ((H : ℝ) - n.val) then
baseStock P n.val - (if n.val = 0 then P.x else baseStock P (n.val - 1))
else 0
/-- Shifting need over a lookahead horizon of `s` periods (Definition 1):
`τ_t^s = (max_{i ∈ ℕ_{t+1}^{t+s}} ∑_{j=t+1}^{i} (q̂_j - k_j))⁺`.
Written as a fold of `max` starting from `0`, which equals the positive part of the
maximum when `s ≥ 1`. -/
noncomputable def shiftingNeed (P : Params H) (s : ℕ) : ℝ :=
(Icc 1 s).fold max 0 (fun i =>
∑ j ∈ univ.filter (fun j : Fin H => 1 ≤ j.val ∧ j.val ≤ i), (uncapOrder P j - P.k j))
/-- Order quantity in the current period `t` under the Lookahead Peak-Shaving policy with
lookahead horizon `s` (Definition 2, eq. (11)): a generalized base-stock policy with lower
base-stock level `Ŝ_t` and upper base-stock level `Ŝ_t + τ_t^s`. The three cases are
continuous at their boundaries, so assigning the boundary points to the next case does
not change the value. -/
noncomputable def lpsOrder [NeZero H] (P : Params H) (s : ℕ) : ℝ :=
if P.x < baseStock P 0 - P.k 0 then baseStock P 0 - P.x
else if P.x < baseStock P 0 + shiftingNeed P s - P.k 0 then P.k 0
else baseStock P 0 + shiftingNeed P s - P.x
end RobustVolumeFlex
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Params (data of one problem instance)
For a natural number (the horizon length; is allowed), an instance is an arbitrary tuple of:
- five real numbers ;
- a real vector , indexed by ;
- an arbitrary set of real vectors .
There are no constraints. Any of may be negative or zero. may be empty, unbounded or non-closed, and its vectors may have negative entries. When , both and every element of are the empty vector, so is either or the one-point set containing the empty vector.
cumSum (partial sums)
For a vector and a natural number ,
For every this is the full sum . If it is the empty sum, . The index ranges over all of , not just .
minCumDemand
For an instance and ,
using the real-number infimum with its conventions for degenerate cases:
- If , then .
- If the set is not bounded below, then (it is not ).
- Otherwise it is the true infimum, which need not be attained by any .
maxCumDemand
For an instance and ,
using the real-number supremum with its conventions for degenerate cases:
- If , then .
- If the set is not bounded above, then (it is not ).
- Otherwise it is the true supremum, which need not be attained.
Because of these conventions, is not guaranteed in degenerate cases. For example, if the set is bounded below with infimum but unbounded above, then and .
IsFeasible
For an instance and three vectors , the triple is feasible when, for every , all of the following hold:
- ;
- ;
- ;
- ;
- .
Here . The vector has no sign constraint and is bounded only from below by the first two inequalities. With the junk values of described above, these constraints still apply as stated.
Every instance has at least one feasible triple: take and large enough. When there are no constraints, and the unique (empty) triple is feasible.
objective
For an instance and vectors ,
When this is .
IsRobustlyOptimal
For an instance , a triple is robustly optimal when:
- is feasible in the sense of
IsFeasible; and - for every triple that is feasible for , we have .
In other words, is a global minimizer of over the feasible set.
- : the unique empty triple is robustly optimal.
- No minimizer: for some instances no triple satisfies the predicate, namely whenever is unbounded below on the feasible set. For example, take , , . Then are the only constraints on , and as .
- Not unique: the predicate does not single out one minimizer.
baseStock
For an instance and ,
- : division by zero yields , so .
- Lower bound: in all cases .
- Large : for the value no longer depends on , because and use full sums.
- Junk inputs: the junk values of enter the formula directly.
uncapOrder
For an instance and an index ,
- The test: is computed in real arithmetic, with . It is applied separately to each , with no reference to whether it held at other indices.
- If , it holds on an initial segment of indices, possibly empty or all of .
- If , it can hold on a final segment instead.
- Previous index: in the second case, is used whether or not the test held at index . The natural-number subtraction only occurs when , so it never truncates.
- Sign:
- For (when the test holds), .
- For , can be negative whenever ; nothing forces to be nondecreasing.
- Domain: is defined only on , so it is vacuous when .
shiftingNeed
For an instance and a natural number , define for each natural number
which is an empty sum () when . The shifting need is the maximum of and these values for :
- : the index range is empty and .
- Sign: always .
- Large : for all are equal to the full sum . So taking larger than changes nothing, and may exceed .
- : all , hence .
- Index 0 excluded: index never enters the sums.
lpsOrder
This is defined only when . For an instance and a natural number , write (which uses only the first demand coordinate, ), and for the first base capacity. The value is
Boundary points go to the later case: falls in the second or third case, and falls in the third.
Write ; note always and . Then the three cases are , , and , and the value is
- Negative : if , the first case always applies and the value is .
- : this happens, for example, when or . The middle case is then empty and the value is .
- Inputs used: the value depends on , on , on , and (through ) on for .
- No link to optimality: the definition makes no reference to
IsFeasibleorIsRobustlyOptimal.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.