Arbitrary setup costs: (Theorem 2)
ProvedOWMR.arbitrary_setup_costsLet . Consider an OWMR network with retailers that satisfies the standing assumptions: demand vectors i.i.d. over periods with nonnegative components and , setup costs (otherwise arbitrary), and . Suppose
- the retailer demands in each period are associated: for all bounded, measurable, coordinatewise nondecreasing ,
- for every retailer , and
- .
Then, for all finite supplier and retailer lead times and from every valid initial state, the deterministic consolidation policy of Definition 2 satisfies
At the factor is , and it decreases to as grows. Unlike Theorem 1, the factor does not depend on the ratio of retailer to supplier setup costs.
Formalization Note The conclusion holds for every admissible choice in Definition 2 (IsConChoice N m c); depends on through these choices. Costs take values in .
import Definitions.Def_owmr_consolidation_policy open scoped ENNReal
namespace OWMR
theorem arbitrary_setup_costs {n : ℕ} (hn : 0 < n) (N : Network n) (hN : N.Standing)
(hA : N.Associated) (m : ℝ) (hm : 1 ≤ m) (hH : ∀ i, m * N.h ≤ N.H i) (hp : N.h ≤ N.p)
(x : InitState n) (hx : x.Valid) (c : ConChoice n) (hc : IsConChoice N m c) :
(conPolicy N x c).avgCost N x ≤ ENNReal.ofReal (13 / 3 + 32 / (57 * m)) * OPT N x := by sorry
end OWMRRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: OWMR.arbitrary_setup_costs
What is asserted. Take any with . Take any network with retailers that satisfies the standing assumptions and the association property. Take any real with for all , and suppose . Finally take any valid initial state and any parameter bundle that satisfies the choice predicate for . Then
The left side is the long-run average cost of the deterministic policy in §5. (§2) is the infimum of the same cost over all admissible policies, randomized ones included. The constant is a real number in . There is no division by zero because , and the constant sits in as itself. It is the same expression that defines the constants in §3.
1. Binders and hypotheses
- , with the hypothesis . Retailers are indexed by .
- is a network with these fields:
- lead times (supplier to warehouse) and (warehouse to retailer ); zero is allowed;
- a probability measure on , the law of one period's demand vector ;
- real numbers (setup cost per warehouse order), (setup cost per shipment to ), (warehouse holding cost), (retailer holding cost) and (backorder cost).
- Standing assumptions: for every , . Also , , , and .
- Association: for all Borel-measurable, bounded, coordinatewise nondecreasing ,
which says . Point masses and product measures (by Harris's inequality) satisfy this.
- with , and for every . In particular every , so can be any value in .
- .
- is the initial state:
- , the warehouse stock;
- , the retailer net inventories;
- , the warehouse pipeline: arrives in period , and is read only for ;
- , the retailer pipelines: arrives at in period , and is read only for .
- Valid: , for all , and for all . There is no constraint on , so negative values (backlog) are allowed. Entries that are never read still have to be .
- is a "consolidation choice" with these fields:
- ;
- batch flags ;
- ;
- a retailer ;
- offsets ;
- a bijection , which enumerates the rationals in .
- The hypothesis , given in §4.
2. Cost functional and OPT
A policy on a randomization space has two components, both functions of and of the whole demand path :
- an order ;
- dispatches .
Arrivals are for and otherwise, and for and otherwise. The end-of-period stocks are
and the period cost is
The long-run average cost is
In this integral are i.i.d. and for . The integral is a lower Lebesgue integral, so it is defined even when the integrand is not measurable. Each period cost is truncated below at .
is the infimum of over all measurable spaces (any type in the base universe, any σ-algebra), all probability measures on , and all policies that satisfy three conditions:
- Nonanticipative: and depend on only through .
- Measurable: for each , and each are measurable in under the product σ-algebra.
- Feasible for every and every demand path, not just almost surely: , , and with . This is equivalent to .
For feasible policies every , so the truncation never acts on the right side.
A deterministic policy is costed with a one-point and the point mass. Nothing in the theorem assumes or claims that is feasible, nonanticipative or measurable. Its cost is simply the formula above applied to its orders and dispatches.
3. Auxiliary objects and constants
- is the law of , and is the law of ; both live on .
- , where is a sum of i.i.d. variables.
- , where is a sum of i.i.d. variables. If this reduces to .
- and are Bochner integrals, so they would take the value if the integrand were not integrable. Under the standing assumptions the integrands are integrable, and .
- Single-location optimum . This is the infimum, over randomizations and order rules that are nonanticipative and jointly measurable, of
Here demands are i.i.d. and the start is . Write .
- cost . This is the same limsup average along the path defined by
- ;
- if , and otherwise;
- ;
- period cost , truncated at .
- Canonical optimum . It holds when all of the following hold, comparing in :
- ;
- ;
- ;
- ;
- for every .
- Best half window . It holds when , , and for every pair meeting the same two constraints. The setup cost is in this comparison.
- Renewal function. . The term equals if and otherwise.
- Constants. , , and . For these satisfy , , and , and every denominator is nonzero.
4. The choice predicate
The predicate is the conjunction of three clauses.
(R) Retailers. For every , set , and . Exactly one of two cases applies.
- If : is false, , and minimizes over .
- If : is true, and there exist reals with . Define the ratio , computed in (so for , , ).
- If , then .
- If , then .
(W) Warehouse.
- If : there exist with , and , . That is, the pair is shifted up so that .
- If : and minimizes .
(O) Offsets. for every .
The retailer and the enumeration are not constrained at all.
How depends on . Only through four constants:
- scales the retailer setup costs used inside and ;
- decides batch versus no batch;
- decides half window versus canonical window;
- scales the warehouse setup cost inside .
The policy itself takes no ; it depends on only through .
5. The policy (left side)
The policy is deterministic. Given a demand path , it computes an internal state recursively:
- is the initial state;
- is the state left by , with then reduced by .
The order and dispatches are the outputs of , so they depend only on . These outputs are costed by §2; the policy's own bookkeeping plays no part in the cost.
State. The state has these components:
- a "running" flag;
- the unallocated warehouse stock ;
- the retailer inventories ;
- scheduled arrivals at the warehouse and at retailer , indexed by absolute period ;
- a FIFO queue of requests, each with a retailer, size , allocated amount, shipped amount, offset and creation period;
- a counter of requests created in phase A.
Initially the flag is off, and is the initial vector. for and otherwise, for and otherwise, the queue is empty and the counter is .
Positions. For a state at period :
- ;
- is the sum of alloc over 's queued requests;
- is the sum of allocshipped over 's queued requests;
- .
. First receive arrivals: and . Let and (natural-number subtraction). Then take the first branch that applies:
- If the flag is on, do a regular step.
- Else if , ship all of to , set , and order .
- Else if , , and for all : turn the flag on. For each with , in index order, append a request of size , offset , created at ; these requests do not increase the counter. Then do a regular step.
- Otherwise order and dispatch .
Regular step, phase A. All quantities are computed on the post-receipt state.
- Each retailer with and creates a request of size .
- The warehouse position is
- The warehouse orders if , and otherwise. The order is booked to arrive at , or added to at once if .
- Each new request gets offset if is false. If is true it gets the offset from the rule below, evaluated on the provisional state (new requests and the order already booked).
Regular step, phase B. Go through the queue in order, starting with . Give each request and set .
- If the request's retailer has false, ship all of its allocated but unshipped stock.
- If is true, ship that stock only when the allocation moves from prev to new in one of three ways, and otherwise keep it reserved:
- ; or
- and ; or
- .
After the pass, and fully shipped requests are dropped. A shipment to is added to at once if , and booked at otherwise. The outputs are and the total shipped to .
Offset rule. It applies to a new batch request of retailer with size at period . Let be the counter before this period plus 's 1-based position among the retailers requesting in this period. Then , where is the least with
and if no such exists. Here is the expectation, over fresh i.i.d. demand vectors drawn from , of the proxy
The proxy is computed by re-running regular steps from the provisional state through periods , with batching switched off for every retailer and the fresh demands. Its terms are:
- is the allocation, after phase B of period , of the first queued request of retailer created at , or if no such request remains;
- , evaluated after phase A of period ;
- if the threshold test with offset passes from to (taking ), and otherwise (taking ).
6. Edge cases
-
. Any already contains , so the existence of forces on its own. With , is a genuine maximum.
-
Values in . Both sides lie in , and . Because :
- if , the claim holds trivially;
- if , the claim says the left side equals .
-
is not excluded. Take a point mass at , , , , , , and . Ordering and dispatching every period is then feasible at zero cost. A valid exists in this instance: false, , .
-
No finiteness claim. No hypothesis bounds the left side, and the theorem asserts only the inequality.
-
Every admissible . The claim holds for every satisfying the predicate: any choice among minimizers, canonical pairs or best windows, any , any enumeration , any .
-
Existence is assumed, not proved. The predicate requires several objects to exist:
- minimizers of and of (the latter with );
- canonical pairs satisfying the exact equalities and , which is possible only if ;
- a minimizing half window.
The theorem does not assert that these exist. For any where no satisfies the predicate, the statement is vacuous for that instance.
-
Range of . Instances with are excluded. A larger admissible gives a smaller constant but changes which are admissible.
-
Zero lead times. These are allowed. If , then and the ship-everything-to- branch runs at .
-
limsup on both sides. Both average costs use limsup, and OPT is an infimum of limsups.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.