Introduction
Single-item dynamic lot sizing is a fundamental problem in inventory and production planning: given deterministic demands d 1 , … , d n d_1,\ldots,d_n d 1 , … , d n over a finite planning horizon of n n n periods, one chooses nonnegative order quantities q 1 , … , q n q_1,\ldots,q_n q 1 , … , q n to satisfy demand without backlogging while minimizing total procurement and inventory holding costs. Under an all-units quantity discount with threshold Q > 0 Q > 0 Q > 0 , ordering 0 ≤ q i < Q 0 \le q_i < Q 0 ≤ q i < Q units in period i i i incurs a regular unit price p 1 , i p_{1,i} p 1 , i , whereas ordering q i ≥ Q q_i \ge Q q i ≥ Q units lowers the unit price on the entire batch to p 2 , i ≤ p 1 , i p_{2,i} \le p_{1,i} p 2 , i ≤ p 1 , i . Because the procurement cost function drops discontinuously at q i = Q q_i = Q q i = Q , purchasing surplus stock to reach the threshold can be strictly cheaper than ordering the exact net demand, even when holding costs are positive and disposal of excess inventory is prohibited.
When both price sequences { p 1 , i } \{p_{1,i}\} { p 1 , i } and { p 2 , i } \{p_{2,i}\} { p 2 , i } are restricted to be non-increasing over time, recent work [11 ] showed that single-item lot sizing with a stationary one-breakpoint all-units discount and zero setup cost can be solved in O ( n log n ) O(n \log n) O ( n log n ) time, even under time-varying post-order capacities. Once prices are allowed to vary arbitrarily over time, however, the structural properties that directly bound physical inventory break down. Ahead of a sharp price increase, an optimal physical schedule may purchase large speculative batches even when incoming inventory already covers several upcoming periods of demand, carrying stock arbitrarily larger than 2 Q 2Q 2 Q . Conversely, when prices subsequently drop, previously accumulated stock competes with newly discounted batches across nonconvex jump discontinuities.
Main results and proof architecture
In this paper we resolve the uncapacitated problem under completely arbitrary nonnegative unit prices 0 ≤ p 2 , i ≤ p 1 , i 0 \le p_{2,i} \le p_{1,i} 0 ≤ p 2 , i ≤ p 1 , i and nonnegative linear holding costs h i ≥ 0 h_i \ge0 h i ≥ 0 , for both continuous (G = R ≥ 0 \mathcal{G} = \mathbb{R}_{\ge0} G = R ≥ 0 ) and integral (G = Z ≥ 0 \mathcal{G} = \mathbb{Z}_{\ge0} G = Z ≥ 0 ) quantity domains. The formal model and arithmetic conventions are stated in § 2 .
Theorem 1.1 (Optimal values in O ( n log n ) O(n \log n) O ( n log n ) time and linear space). For any n n n -period uncapacitated instance satisfying (2.1)–(2.3), the minimum total cost O P T \mathrm{OPT} OPT with free terminal inventory, together with the zero-terminal prefix optimum O P T k , 0 \mathrm{OPT}_{k,0} OPT k , 0 for every k ∈ { 1 , … , n } k \in\{1,\ldots,n\} k ∈ { 1 , … , n } , can be computed online in O ( n log n ) O(n \log n) O ( n log n ) time and O ( n ) O(n) O ( n ) working space. These bounds hold for both G = R ≥ 0 \mathcal{G} = \mathbb{R}_{\ge0} G = R ≥ 0 and G = Z ≥ 0 \mathcal{G} = \mathbb{Z}_{\ge0} G = Z ≥ 0 under the unit-cost exact arithmetic model.
Theorem 1.2 (Optimal physical schedule recovery). Under the hypotheses of Theorem 1.1 , an optimal physical order sequence ( q 1 , … , q n ) ∈ G n (q_1,\ldots,q_n) \in\mathcal{G}^n ( q 1 , … , q n ) ∈ G n for the free-terminal problem—or for any prescribed zero-terminal prefix 1 , … , k 1,\ldots,k 1 , … , k —can be computed in O ( n log n ) O(n \log n) O ( n log n ) time and O ( n log n ) O(n \log n) O ( n log n ) space.
The proof is organized around three main steps that decouple speculative physical stockpiling from compressed frontier maintenance:
Online effective-price reduction and retroactive aggregation (Section 2.2). At each period i i i , we maintain in O ( 1 ) O(1) O ( 1 ) time the cheapest holding-cost-adjusted historical regular price α i \alpha_i α i and discounted price β i \beta_i β i , together with their attaining origin periods s ( i ) , r ( i ) ≤ i s(i), r(i) \le i s ( i ) , r ( i ) ≤ i . Replacing ( p 1 , i , p 2 , i ) (p_{1,i},p_{2,i}) ( p 1 , i , p 2 , i ) by ( α i , β i ) (\alpha_i,\beta_i) ( α i , β i ) defines a virtual lot-sizing problem whose prices are no longer arbitrary: they satisfy the non-speculative inequalities α i + 1 ≤ α i + h i \alpha_{i+1} \le\alpha_i + h_i α i + 1 ≤ α i + h i and β i + 1 ≤ β i + h i \beta_{i+1} \le\beta_i + h_i β i + 1 ≤ β i + h i . Theorem 2.2 proves that the virtual and physical problems have identical free-terminal and zero-terminal optima on every horizon prefix. Crucially, routing virtual orders back to their origin periods ( s ( i ) , r ( i ) ) (s(i),r(i)) ( s ( i ) , r ( i )) and aggregating colliding orders never worsens price tiers: combining regular orders that cross Q Q Q only unlocks a cheaper discounted rate p 2 , t ≤ p 1 , t p_{2,t} \le p_{1,t} p 2 , t ≤ p 1 , t , while discounted virtual orders already have size at least Q Q Q .
Simultaneous normal form under non-speculative prices (Sections 2.3–2.4). Unlike monotone prices (β i + 1 ≤ β i \beta_{i+1} \le\beta_i β i + 1 ≤ β i ), non-speculative effective prices permit α i + 1 > α i \alpha_{i+1} > \alpha_i α i + 1 > α i and β i + 1 > β i \beta_{i+1} > \beta_i β i + 1 > β i when h i > 0 h_i > 0 h i > 0 . By accounting jointly for procurement and cumulative holding savings during tier-preserving history trimming, we prove that minimizing the virtual inventory potential Φ ( I ^ ) = ∑ t = 1 m I ^ t \Phi(\hat{I}) = \sum_{t=1}^{m} \hat{I}_t Φ ( I ^ ) = ∑ t = 1 m I ^ t yields one optimal virtual schedule that simultaneously satisfies q ^ i > 0 ⟹ I ^ i − 1 < d i \hat{q}_i > 0 \Longrightarrow\hat{I}_{i-1} < d_i q ^ i > 0 ⟹ I ^ i − 1 < d i , I ^ i − 1 < 2 Q \hat{I}_{i-1} < 2Q I ^ i − 1 < 2 Q , and I ^ n < Q \hat{I}_n < Q I ^ n < Q . This justifies an auxiliary dynamic program supported on [ 0 , 2 Q ] [0,2Q] [ 0 , 2 Q ] that overestimates certain positive-inventory states without altering O P T \mathrm{OPT} OPT or any O P T k , 0 \mathrm{OPT}_{k,0} OPT k , 0 . Subtracting β i y \beta_i y β i y makes the regular departure envelope nondecreasing above Q Q Q and the discounted envelope nonincreasing, establishing a single takeover crossover even across downward discount jumps.
Certified one-kink frontier and amortized balanced tree (Sections 3–5). We represent the auxiliary frontier as the lower envelope of interleaved one-kink candidate curves stored in an augmented height-balanced search tree. Adjacent dominance under regular-price updates is governed by an exact three-regime signed comparator threshold θ j \theta_j θ j that translates uniformly by + h i +h_i + h i under holding shifts. Bulk discounted transitions reduce to prefix-record minima of parallel rays normalized lazily via frozen successor-anchor snapshots, and merges locate the unique takeover coordinate in O ( log n ) O(\log n) O ( log n ) time via a bracket-guarded binary search. Every nonterminal loop step permanently deletes a candidate node, bounding the total number of structural tree events by O ( n ) O(n) O ( n ) . Two-stage recovery combines path-copying persistence on the auxiliary frontier with O ( n ) O(n) O ( n ) origin aggregation.
Relation to prior work
Dynamic lot sizing originates with Wagner and Whitin [13 ] , who gave an O ( n 2 ) O(n^2) O ( n 2 ) forward algorithm for uncapacitated lot sizing with fixed setup costs and stationary or monotone unit costs. Nearly three decades later, Wagelmans, van Hoesel, and Kolen [12 ] and Aggarwal and Park [1 ] independently improved the classical uncapacitated Wagner–Whitin problem with arbitrary time-varying unit production costs to O ( n log n ) O(n\log n) O ( n log n ) time via geometric envelope maintenance and Monge-array techniques; see also Chung and Lin [5 ] and Atamtürk and Hochbaum [2 ] for polynomial algorithms in structured capacitated settings.
Lot sizing under quantity discounts introduces a fundamentally different nonconvexity because the cost break occurs at a positive threshold Q > 0 Q > 0 Q > 0 rather than at zero. Federgruen and Lee [6 ] analyzed uncapacitated dynamic lot sizing with setup costs and stationary or nonincreasing cost parameters, obtaining an O ( n 2 ) O(n^2) O ( n 2 ) algorithm for incremental discounts and an O ( n 3 ) O(n^3) O ( n 3 ) algorithm for a one-breakpoint all-units discount. Extensions incorporating resale or capacitated setup structures require higher-degree polynomial bounds, such as O ( n 4 ) O(n^4) O ( n 4 ) in Malekian, Mirmohammadi, and Bijari [8 ] .
For uncapacitated lot sizing with general time-varying piecewise-linear or piecewise-concave procurement costs and m m m stationary breakpoints, Koca, Yaman, and Aktürk [7 ] established polynomial solvability in O ( n 2 m + 3 ) O(n^{2m+3}) O ( n 2 m + 3 ) time (O ( n 5 ) O(n^5) O ( n 5 ) for m = 1 m = 1 m = 1 ). Ou [9 ] improved the piecewise-linear bound to O ( n m + 2 log n ) O(n^{m+2}\log n) O ( n m + 2 log n ) (O ( n 3 log n ) O(n^3\log n) O ( n 3 log n ) for m = 1 m = 1 m = 1 ) using range-minimum queries, and Papadopoulos [10 ] removed the logarithmic factor to obtain O ( n m + 2 ) O(n^{m+2}) O ( n m + 2 ) (O ( n 3 ) O(n^3) O ( n 3 ) for m = 1 m = 1 m = 1 ). Those general formulations allow nonzero fixed setup intercepts on each segment. When setup costs are absent and the nonconvexity stems purely from a one-breakpoint all-units discount, Papadopoulos [11 ] achieved O ( n log n ) O(n\log n) O ( n log n ) time under non-increasing unit prices. Table 1 summarizes representative exact complexity bounds; the present work shows that in the uncapacitated setting without setup costs, removing price monotonicity entirely incurs no asymptotic overhead beyond O ( n log n ) O(n\log n) O ( n log n ) .
For balanced search trees and split/join primitives, we rely on standard augmented tree techniques [4 ] and the join-based framework of Blelloch, Ferizovic, and Sun [3 ] . All problem-specific invariants, cached thresholds, and lazy propagation operators are self-contained below.
Model, Effective-Price Reduction, and Auxiliary Recurrence
Problem formulation
Consider a finite horizon of n ≥ 1 n \ge1 n ≥ 1 periods indexed by i = 1 , … , n i = 1,\ldots,n i = 1 , … , n . Let G = R ≥ 0 \mathcal{G} = \mathbb{R}_{\ge0} G = R ≥ 0 in the continuous model and G = Z ≥ 0 \mathcal{G} = \mathbb{Z}_{\ge0} G = Z ≥ 0 in the integral model. In period i i i , deterministic demand is d i ∈ G d_i \in\mathcal{G} d i ∈ G , the holding cost per unit of inventory remaining after demand is h i ≥ 0 h_i \ge0 h i ≥ 0 , and the common all-units discount threshold is Q ∈ G Q \in\mathcal{G} Q ∈ G with Q > 0 Q > 0 Q > 0 . The regular unit price p 1 , i p_{1,i} p 1 , i and discounted unit price p 2 , i p_{2,i} p 2 , i are arbitrary finite real numbers satisfying only the within-period discount ordering
0 ≤ p 2 , i ≤ p 1 , i < + ∞ , i = 1 , … , n . (1) 0 \le p_{2,i} \le p_{1,i} < +\infty,\qquad i = 1,\ldots,n. \tag*{(1)} 0 ≤ p 2 , i ≤ p 1 , i < + ∞ , i = 1 , … , n . (1)
Table 1. Comparison of exact time complexities for related single-item lot-sizing models over n n n periods.
No temporal monotonicity is assumed across periods. The procurement cost of ordering q ∈ G q \in\mathcal{G} q ∈ G units in period i i i is
P i ( q ) = { p 1 , i q , 0 ≤ q < Q , p 2 , i q , q ≥ Q . (2) P_i(q) =
\begin{cases}
p_{1,i}q, & 0 \le q < Q,\\
p_{2,i}q, & q \ge Q.
\end{cases} \tag*{(2)} P i ( q ) = { p 1 , i q , p 2 , i q , 0 ≤ q < Q , q ≥ Q . (2)
Note that P i ( 0 ) = 0 P_i(0)=0 P i ( 0 ) = 0 and P i P_i P i is subadditive: P i ( q + r ) ≤ P i ( q ) + P i ( r ) P_i(q+r) \le P_i(q)+P_i(r) P i ( q + r ) ≤ P i ( q ) + P i ( r ) for all q , r ≥ 0 q,r \ge0 q , r ≥ 0 , because q + r < Q q+r<Q q + r < Q keeps both summands in the regular tier whereas q + r ≥ Q q+r \ge Q q + r ≥ Q prices the combined batch at p 2 , i ≤ p 1 , i p_{2,i} \le p_{1,i} p 2 , i ≤ p 1 , i .
For any prefix horizon k ∈ { 1 , … , n } k \in\{1,\ldots,n\} k ∈ { 1 , … , n } , an order sequence q = ( q 1 , … , q k ) ∈ G k q=(q_1,\ldots,q_k) \in\mathcal{G}^k q = ( q 1 , … , q k ) ∈ G k and its induced inventory sequence I = ( I 0 , I 1 , … , I k ) ∈ G k + 1 I=(I_0,I_1,\ldots,I_k) \in\mathcal{G}^{k+1} I = ( I 0 , I 1 , … , I k ) ∈ G k + 1 are feasible if
I 0 = 0 , I i = I i − 1 + q i − d i ≥ 0 , q i ≥ 0 , i = 1 , … , k . (3) I_0=0,\qquad I_i=I_{i-1}+q_i-d_i \ge0,\qquad q_i \ge0,\qquad i=1,\ldots,k. \tag*{(3)} I 0 = 0 , I i = I i − 1 + q i − d i ≥ 0 , q i ≥ 0 , i = 1 , … , k . (3)
There is no upper capacity on I i I_i I i or q i q_i q i , and no disposal or resale operation. The total cost on prefix 1 , … , k 1,\ldots,k 1 , … , k is
J k ( q , I ) = ∑ i = 1 k ( P i ( q i ) + h i I i ) . (4) J_k(q,I)=\sum_{i=1}^{k}\left(P_i(q_i)+h_iI_i\right). \tag*{(4)} J k ( q , I ) = i = 1 ∑ k ( P i ( q i ) + h i I i ) . (4)
We denote by OPT k \operatorname{OPT}_k OPT k the minimum of J k ( q , I ) J_k(q,I) J k ( q , I ) over all feasible schedules on 1 , … , k 1,\ldots,k 1 , … , k with free terminal inventory I k ≥ 0 I_k \ge0 I k ≥ 0 , writing OPT = OPT n \operatorname{OPT}=\operatorname{OPT}_n OPT = OPT n for the full horizon, and by OPT k , 0 \operatorname{OPT}_{k,0} OPT k , 0 the minimum of J k ( q , I ) J_k(q,I) J k ( q , I ) subject to the additional terminal constraint I k = 0 I_k=0 I k = 0 .
Our complexity bounds use a unit-cost exact real-arithmetic model in which elementary arithmetic operations (+ + + , − - − , × \times × , ÷ \div ÷ ) and comparisons take O ( 1 ) O(1) O ( 1 ) time, supplemented in the integer model G = Z ≥ 0 \mathcal{G}=\mathbb{Z}_{\ge0} G = Z ≥ 0 by O ( 1 ) O(1) O ( 1 ) -time exact floor and ceiling operations. Throughout, we write log n \log n log n for max { 1 , log 2 n } \max\{1,\log_2 n\} max { 1 , log 2 n } .
Lemma 2.1 (Existence of optimal physical schedules). For every k ∈ { 1 , … , n } k \in\{1,\ldots,n\} k ∈ { 1 , … , n } , both OPT k \operatorname{OPT}_k OPT k and OPT k , 0 \operatorname{OPT}_{k,0} OPT k , 0 are finite and attained by feasible schedules satisfying ∑ i = 1 k q i ≤ D k + Q \sum_{i=1}^{k}q_i \le D_k+Q ∑ i = 1 k q i ≤ D k + Q , where D k = ∑ i = 1 k d i D_k=\sum_{i=1}^{k}d_i D k = ∑ i = 1 k d i .
Proof. Ordering q i = d i q_i=d_i q i = d i for each i = 1 , … , k i=1,\ldots,k i = 1 , … , k yields I i = 0 I_i=0 I i = 0 throughout, so both feasible sets are nonempty and have finite infima. For I k = 0 I_k=0 I k = 0 , every feasible schedule satisfies ∑ i = 1 k q i = D k \sum_{i=1}^{k}q_i=D_k ∑ i = 1 k q i = D k , confining ( q 1 , … , q k ) (q_1,\ldots,q_k) ( q 1 , … , q k ) to [ 0 , D k ] [0,D_k] [ 0 , D k ] . For free I k ≥ 0 I_k \ge0 I k ≥ 0 , suppose a feasible schedule has I k ≥ Q I_k \ge Q I k ≥ Q . Let j ≤ k j \le k j ≤ k be the first period with ∑ t = 1 j q t > D k \sum_{t=1}^{j}q_t>D_k ∑ t = 1 j q t > D k , and put ℓ = D k − ∑ t = 1 j − 1 q t ∈ [ 0 , q j ) \ell=D_k-\sum_{t=1}^{j-1}q_t\in[0,q_j) ℓ = D k − ∑ t = 1 j − 1 q t ∈ [ 0 , q j ) . Keeping q 1 , … , q j − 1 q_1,\ldots,q_{j-1} q 1 , … , q j − 1 , zeroing q j + 1 , … , q k q_{j+1},\ldots,q_k q j + 1 , … , q k , and replacing q j q_j q j by ℓ \ell ℓ (if q j < Q q_j<Q q j < Q or ℓ = 0 \ell=0 ℓ = 0 ) or max { ℓ , Q } \max\{\ell,Q\} max { ℓ , Q } (if q j ≥ Q q_j\ge Q q j ≥ Q and ℓ > 0 \ell>0 ℓ > 0 ) preserves feasibility in G k \mathcal{G}^k G k , keeps q j ′ q'_j q j ′ in its original price tier (or zero), lowers all inventories I t ′ ≤ I t I'_t\le I_t I t ′ ≤ I t , and achieves I k ′ < Q I'_k<Q I k ′ < Q with J k ( q ′ , I ′ ) ≤ J k ( q , I ) J_k(q',I')\le J_k(q,I) J k ( q ′ , I ′ ) ≤ J k ( q , I ) because p 2 , t ≥ 0 p_{2,t}\ge0 p 2 , t ≥ 0 and h t ≥ 0 h_t\ge0 h t ≥ 0 . Hence we may restrict attention to the bounded set ∑ i = 1 k q i ≤ D k + Q \sum_{i=1}^k q_i\le D_k+Q ∑ i = 1 k q i ≤ D k + Q . In Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 this set is finite; in R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 it is compact and each P i P_i P i is lower semicontinuous at its downward jump Q Q Q , so the minimum is attained.
Online effective-price envelope and retroactive order aggregation
For 1 ≤ t ≤ i ≤ n + 1 1\le t\le i\le n+1 1 ≤ t ≤ i ≤ n + 1 , define the cumulative holding charge from period t t t to the start of period i i i by
H ( t , i ) = ∑ m = t i − 1 h m , (5) H(t,i)=\sum_{m=t}^{i-1}h_m, \tag*{(5)} H ( t , i ) = m = t ∑ i − 1 h m , (5)
with H ( i , i ) = 0 H(i,i)=0 H ( i , i ) = 0 . Carrying one unit purchased in period t t t through periods t , … , i − 1 t,\ldots,i-1 t , … , i − 1 adds exactly H ( t , i ) H(t,i) H ( t , i ) to its unit procurement cost when it arrives at period i i i . Define the effective unit prices ( α i , β i ) (\alpha_i,\beta_i) ( α i , β i ) and their origin pointers ( s ( i ) , r ( i ) ) (s(i),r(i)) ( s ( i ) , r ( i )) recursively in O ( 1 ) O(1) O ( 1 ) time per period:
α 1 = p 1 , 1 , s ( 1 ) = 1 ; α i = min { α i − 1 + h i − 1 , p 1 , i } , s ( i ) = { i , p 1 , i ≤ α i − 1 + h i − 1 , s ( i − 1 ) , otherwise , (6) \alpha_1=p_{1,1},\quad s(1)=1;\qquad\alpha_i=\min\{\alpha_{i-1}+h_{i-1},p_{1,i}\},\quad s(i)=
\begin{cases}
i, & p_{1,i}\le\alpha_{i-1}+h_{i-1},\\
s(i-1), & \text{otherwise},
\end{cases} \tag*{(6)} α 1 = p 1 , 1 , s ( 1 ) = 1 ; α i = min { α i − 1 + h i − 1 , p 1 , i } , s ( i ) = { i , s ( i − 1 ) , p 1 , i ≤ α i − 1 + h i − 1 , otherwise , (6)
β 1 = p 2 , 1 , r ( 1 ) = 1 ; β i = min { β i − 1 + h i − 1 , p 2 , i } , r ( i ) = { i , p 2 , i ≤ β i − 1 + h i − 1 , r ( i − 1 ) , otherwise , (7) \beta_1=p_{2,1},\quad r(1)=1;\qquad\beta_i=\min\{\beta_{i-1}+h_{i-1},p_{2,i}\},\quad r(i)=
\begin{cases}
i, & p_{2,i}\le\beta_{i-1}+h_{i-1},\\
r(i-1), & \text{otherwise},
\end{cases} \tag*{(7)} β 1 = p 2 , 1 , r ( 1 ) = 1 ; β i = min { β i − 1 + h i − 1 , p 2 , i } , r ( i ) = { i , r ( i − 1 ) , p 2 , i ≤ β i − 1 + h i − 1 , otherwise , (7)
for i = 2 , … , n i=2,\ldots,n i = 2 , … , n . Unrolling the recurrences immediately yields
α i = min 1 ≤ t ≤ i { p 1 , t + H ( t , i ) } = p 1 , s ( i ) + H ( s ( i ) , i ) , β i = min 1 ≤ t ≤ i { p 2 , t + H ( t , i ) } = p 2 , r ( i ) + H ( r ( i ) , i ) . (8) \alpha_i=\min_{1\le t\le i}\{p_{1,t}+H(t,i)\}=p_{1,s(i)}+H(s(i),i),\qquad
\beta_i=\min_{1\le t\le i}\{p_{2,t}+H(t,i)\}=p_{2,r(i)}+H(r(i),i). \tag*{(8)} α i = 1 ≤ t ≤ i min { p 1 , t + H ( t , i )} = p 1 , s ( i ) + H ( s ( i ) , i ) , β i = 1 ≤ t ≤ i min { p 2 , t + H ( t , i )} = p 2 , r ( i ) + H ( r ( i ) , i ) . (8)
Because 0 ≤ p 2 , t ≤ p 1 , t 0\le p_{2,t}\le p_{1,t} 0 ≤ p 2 , t ≤ p 1 , t and h m ≥ 0 h_m\ge0 h m ≥ 0 , the effective prices satisfy the non-speculative inequalities
0 ≤ β i ≤ α i < + ∞ ( 1 ≤ i ≤ n ) , α i + 1 ≤ α i + h i , β i + 1 ≤ β i + h i ( 1 ≤ i < n ) . (9) 0\le\beta_i\le\alpha_i<+\infty\quad(1\le i\le n),\qquad
\alpha_{i+1}\le\alpha_i+h_i,\quad\beta_{i+1}\le\beta_i+h_i\quad(1\le i<n). \tag*{(9)} 0 ≤ β i ≤ α i < + ∞ ( 1 ≤ i ≤ n ) , α i + 1 ≤ α i + h i , β i + 1 ≤ β i + h i ( 1 ≤ i < n ) . (9)
Define the virtual procurement cost in period i i i by
P ^ i ( q ^ ) = { α i q ^ , 0 ≤ q ^ < Q , β i q ^ , q ^ ≥ Q , (10) \widehat{P}_i(\widehat{q})=
\begin{cases}
\alpha_i\widehat{q}, & 0\le\widehat{q}<Q,\\
\beta_i\widehat{q}, & \widehat{q}\ge Q,
\end{cases} \tag*{(10)} P i ( q ) = { α i q , β i q , 0 ≤ q < Q , q ≥ Q , (10)
and for any feasible virtual schedule ( q ^ , I ^ ) (\widehat{q},\widehat{I}) ( q , I ) satisfying (2.3) on 1 , … , k 1,\ldots,k 1 , … , k , define its virtual objective by
J ^ k ( q ^ , I ^ ) = ∑ i = 1 k ( P ^ i ( q ^ i ) + h i I ^ i ) . (11) \widehat{J}_k(\widehat{q},\widehat{I})=\sum_{i=1}^{k}\left(\widehat{P}_i(\widehat{q}_i)+h_i\widehat{I}_i\right). \tag*{(11)} J k ( q , I ) = i = 1 ∑ k ( P i ( q i ) + h i I i ) . (11)
Denote its free-terminal and zero-terminal minima on 1 , … , k 1,\ldots,k 1 , … , k by O P T ^ k \widehat{\mathrm{OPT}}_k OPT k and O P T ^ k , 0 \widehat{\mathrm{OPT}}_{k,0} OPT k , 0 .
Theorem 2.2 (Equivalence of the virtual model and O ( k ) O(k) O ( k ) physical schedule mapping). For every prefix k ∈ { 1 , … , n } k\in\{1,\ldots,n\} k ∈ { 1 , … , n } ,
O P T k = O P T ^ k and O P T k , 0 = O P T ^ k , 0 . (12) \mathrm{OPT}_k=\widehat{\mathrm{OPT}}_k\qquad\text{and}\qquad\mathrm{OPT}_{k,0}=\widehat{\mathrm{OPT}}_{k,0}. \tag*{(12)} OPT k = OPT k and OPT k , 0 = OPT k , 0 . (12)
Specifically, given any feasible virtual schedule ( q ^ 1 , … , q ^ k ) ∈ G k (\hat{q}_1,\ldots,\hat{q}_k)\in G^k ( q ^ 1 , … , q ^ k ) ∈ G k with virtual inventories ( I ^ 0 , … , I ^ k ) (\hat{I}_0,\ldots,\hat{I}_k) ( I ^ 0 , … , I ^ k ) , assign each positive virtual order q ^ i > 0 \hat{q}_i>0 q ^ i > 0 to the origin period
τ ( i ) = { s ( i ) , 0 < q ^ i < Q , r ( i ) , q ^ i ≥ Q , (13) \tau(i)=
\begin{cases}
s(i), & 0<\hat{q}_i<Q,\\
r(i), & \hat{q}_i\ge Q,
\end{cases} \tag*{(13)} τ ( i ) = { s ( i ) , r ( i ) , 0 < q ^ i < Q , q ^ i ≥ Q , (13)
and define the physical order sequence ( q 1 , … , q k ) ∈ G k (q_1,\ldots,q_k)\in G^k ( q 1 , … , q k ) ∈ G k by
q t = ∑ 1 ≤ i ≤ k q ^ i > 0 , τ ( i ) = t q ^ i , t = 1 , … , k . (14) q_t=\sum_{\substack{1\le i\le k\\ \hat{q}_i>0,\ \tau(i)=t}}\hat{q}_i,\qquad t=1,\ldots,k. \tag*{(14)} q t = 1 ≤ i ≤ k q ^ i > 0 , τ ( i ) = t ∑ q ^ i , t = 1 , … , k . (14)
Then ( q 1 , … , q k ) (q_1,\ldots,q_k) ( q 1 , … , q k ) is feasible on 1 , … , k 1,\ldots,k 1 , … , k , induces physical inventories satisfying I m ≥ I ^ m ≥ 0 I_m\ge\hat{I}_m\ge0 I m ≥ I ^ m ≥ 0 for all 1 ≤ m ≤ k 1\le m\le k 1 ≤ m ≤ k with terminal equality I k = I ^ k I_k=\hat{I}_k I k = I ^ k , is computable in O ( k ) O(k) O ( k ) time, and satisfies
J k ( q , I ) ≤ J ^ k ( q ^ , I ^ ) . (15) J_k(q,I)\le\hat{J}_k(\hat{q},\hat{I}). \tag*{(15)} J k ( q , I ) ≤ J ^ k ( q ^ , I ^ ) . (15)
Proof. Since α i ≤ p 1 , i \alpha_i\le p_{1,i} α i ≤ p 1 , i and β i ≤ p 2 , i \beta_i\le p_{2,i} β i ≤ p 2 , i for every i i i , we have P ^ i ( q i ) ≤ P i ( q i ) \hat{P}_i(q_i)\le P_i(q_i) P ^ i ( q i ) ≤ P i ( q i ) for every feasible physical schedule ( q , I ) (q,I) ( q , I ) , giving J ^ k ( q , I ) ≤ J k ( q , I ) \hat{J}_k(q,I)\le J_k(q,I) J ^ k ( q , I ) ≤ J k ( q , I ) and hence OPT ^ k ≤ OPT k \widehat{\operatorname{OPT}}_k\le\operatorname{OPT}_k OPT k ≤ OPT k and OPT ^ k , 0 ≤ OPT k , 0 \widehat{\operatorname{OPT}}_{k,0}\le\operatorname{OPT}_{k,0} OPT k , 0 ≤ OPT k , 0 . Conversely, fix a feasible virtual schedule ( q ^ , I ^ ) (\hat{q},\hat{I}) ( q ^ , I ^ ) on 1 , … , k 1,\ldots,k 1 , … , k and construct ( q 1 , … , q k ) (q_1,\ldots,q_k) ( q 1 , … , q k ) by (2.13)–(2.14). Clearly q t ∈ G q_t\in G q t ∈ G because G G G is closed under nonnegative addition, and bucket-summing by τ ( i ) ∈ { 1 , … , i } \tau(i)\in\{1,\ldots,i\} τ ( i ) ∈ { 1 , … , i } takes O ( k ) O(k) O ( k ) time. Because τ ( i ) ≤ i \tau(i)\le i τ ( i ) ≤ i for every positive virtual order, for each m ∈ { 1 , … , k } m\in\{1,\ldots,k\} m ∈ { 1 , … , k } we have
∑ t = 1 m q t = ∑ 1 ≤ i ≤ k q ^ i > 0 , τ ( i ) ≤ m q ^ i = ∑ i = 1 m q ^ i + ∑ m < i ≤ k q ^ i > 0 , τ ( i ) ≤ m q ^ i . \sum_{t=1}^{m}q_t
=
\sum_{\substack{1\le i\le k\\ \hat{q}_i>0,\ \tau(i)\le m}}\hat{q}_i
=
\sum_{i=1}^{m}\hat{q}_i+
\sum_{\substack{m<i\le k\\ \hat{q}_i>0,\ \tau(i)\le m}}\hat{q}_i. t = 1 ∑ m q t = 1 ≤ i ≤ k q ^ i > 0 , τ ( i ) ≤ m ∑ q ^ i = i = 1 ∑ m q ^ i + m < i ≤ k q ^ i > 0 , τ ( i ) ≤ m ∑ q ^ i .
Subtracting D m = ∑ t = 1 m d t D_m=\sum_{t=1}^{m}d_t D m = ∑ t = 1 m d t yields the physical inventory at the end of period m m m :
I m = I ^ m + ∑ m < i ≤ k q ^ i > 0 , τ ( i ) ≤ m q ^ i ≥ I ^ m ≥ 0. (16) I_m=\hat{I}_m+
\sum_{\substack{m<i\le k\\ \hat{q}_i>0,\ \tau(i)\le m}}\hat{q}_i
\ge\hat{I}_m\ge0. \tag*{(16)} I m = I ^ m + m < i ≤ k q ^ i > 0 , τ ( i ) ≤ m ∑ q ^ i ≥ I ^ m ≥ 0. (16)
Thus ( q , I ) (q,I) ( q , I ) satisfies (2.3), and for m = k m=k m = k the second sum in (2.16) is empty, proving I k = I ^ k I_k=\hat{I}_k I k = I ^ k . Multiplying (2.16) by h m h_m h m , summing over m = 1 , … , k m=1,\ldots,k m = 1 , … , k , and exchanging the order of summation gives
∑ m = 1 k h m I m = ∑ m = 1 k h m I ^ m + ∑ 1 ≤ i ≤ k q ^ i > 0 q ^ i ∑ m = τ ( i ) i − 1 h m = ∑ m = 1 k h m I ^ m + ∑ 1 ≤ i ≤ k q ^ i > 0 H ( τ ( i ) , i ) q ^ i . (17) \sum_{m=1}^{k}h_m I_m
=
\sum_{m=1}^{k}h_m\hat{I}_m+
\sum_{\substack{1\le i\le k\\ \hat{q}_i>0}}\hat{q}_i\sum_{m=\tau(i)}^{i-1}h_m
=
\sum_{m=1}^{k}h_m\hat{I}_m+
\sum_{\substack{1\le i\le k\\ \hat{q}_i>0}}H(\tau(i),i)\hat{q}_i. \tag*{(17)} m = 1 ∑ k h m I m = m = 1 ∑ k h m I ^ m + 1 ≤ i ≤ k q ^ i > 0 ∑ q ^ i m = τ ( i ) ∑ i − 1 h m = m = 1 ∑ k h m I ^ m + 1 ≤ i ≤ k q ^ i > 0 ∑ H ( τ ( i ) , i ) q ^ i . (17)
Next, fix any period t ∈ { 1 , … , k } t\in\{1,\ldots,k\} t ∈ { 1 , … , k } and let T t = { i ∈ { 1 , … , k } : q ^ i > 0 , τ ( i ) = t } T_t=\{i\in\{1,\ldots,k\}:\hat{q}_i>0,\ \tau(i)=t\} T t = { i ∈ { 1 , … , k } : q ^ i > 0 , τ ( i ) = t } , so q t = ∑ i ∈ T t q ^ i q_t=\sum_{i\in T_t}\hat{q}_i q t = ∑ i ∈ T t q ^ i .
If T t = ∅ T_t=\varnothing T t = ∅ , then q t = 0 q_t=0 q t = 0 and P t ( q t ) = 0 P_t(q_t)=0 P t ( q t ) = 0 .
If 0 < q t < Q 0<q_t<Q 0 < q t < Q , then every i ∈ T t i\in T_t i ∈ T t satisfies 0 < q ^ i < Q 0<\hat{q}_i<Q 0 < q ^ i < Q , so t = τ ( i ) = s ( i ) t=\tau(i)=s(i) t = τ ( i ) = s ( i ) and (2.8) gives p 1 , t = α i − H ( t , i ) p_{1,t}=\alpha_i-H(t,i) p 1 , t = α i − H ( t , i ) . Hence
P t ( q t ) = p 1 , t q t = ∑ i ∈ T t ( α i − H ( τ ( i ) , i ) ) q ^ i = ∑ i ∈ T t ( P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i ) . P_t(q_t)=p_{1,t}q_t=\sum_{i\in T_t}\bigl(\alpha_i-H(\tau(i),i)\bigr)\hat{q}_i
=\sum_{i\in T_t}\bigl(\hat{P}_i(\hat{q}_i)-H(\tau(i),i)\hat{q}_i\bigr). P t ( q t ) = p 1 , t q t = i ∈ T t ∑ ( α i − H ( τ ( i ) , i ) ) q ^ i = i ∈ T t ∑ ( P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i ) .
If q t ≥ Q q_t\ge Q q t ≥ Q , the aggregated physical order qualifies for the discounted tier p 2 , t p_{2,t} p 2 , t , so P t ( q t ) = p 2 , t q t P_t(q_t)=p_{2,t}q_t P t ( q t ) = p 2 , t q t . For each i ∈ T t i\in T_t i ∈ T t , either q ^ i ≥ Q \hat{q}_i\ge Q q ^ i ≥ Q , in which case t = r ( i ) t=r(i) t = r ( i ) and p 2 , t q ^ i = ( β i − H ( t , i ) ) q ^ i = P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i p_{2,t}\hat{q}_i=(\beta_i-H(t,i))\hat{q}_i=\hat{P}_i(\hat{q}_i)-H(\tau(i),i)\hat{q}_i p 2 , t q ^ i = ( β i − H ( t , i )) q ^ i = P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i ; or 0 < q ^ i < Q 0<\hat{q}_i<Q 0 < q ^ i < Q , in which case t = s ( i ) t=s(i) t = s ( i ) and p 2 , t ≤ p 1 , t = α i − H ( t , i ) p_{2,t}\le p_{1,t}=\alpha_i-H(t,i) p 2 , t ≤ p 1 , t = α i − H ( t , i ) , so p 2 , t q ^ i ≤ P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i p_{2,t}\hat{q}_i\le\hat{P}_i(\hat{q}_i)-H(\tau(i),i)\hat{q}_i p 2 , t q ^ i ≤ P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i . Summing over i ∈ T t i\in T_t i ∈ T t gives
P t ( q t ) ≤ ∑ i ∈ T t ( P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i ) . P_t(q_t)\le\sum_{i\in T_t}\bigl(\hat{P}_i(\hat{q}_i)-H(\tau(i),i)\hat{q}_i\bigr). P t ( q t ) ≤ i ∈ T t ∑ ( P ^ i ( q ^ i ) − H ( τ ( i ) , i ) q ^ i ) .
Summing this bound over t = 1 , … , k t=1,\ldots,k t = 1 , … , k and adding (17) cancels every H ( τ ( i ) , i ) q ^ i H(\tau(i),i)\hat{q}_i H ( τ ( i ) , i ) q ^ i term, yielding (15) and completing the proof of (12) .
Remark 2.3 (Offline zero-holding-cost reduction via summation by parts). When the entire horizon n n n is known in advance, substituting I i = ∑ t = 1 i q t − D i I_i=\sum_{t=1}^{i}q_t-D_i I i = ∑ t = 1 i q t − D i into (4) and setting H t = ∑ i = t n h i H_t=\sum_{i=t}^{n}h_i H t = ∑ i = t n h i yields J n ( q , I ) = ∑ t = 1 n P ~ t ( q t ) − ∑ t = 1 n H t d t J_n(q,I)=\sum_{t=1}^{n}\widetilde{P}_t(q_t)-\sum_{t=1}^{n}H_td_t J n ( q , I ) = ∑ t = 1 n P t ( q t ) − ∑ t = 1 n H t d t , where P ~ t \widetilde{P}_t P t has zero holding costs and unit prices a ~ t = p 1 , t + H t \tilde{a}_t=p_{1,t}+H_t a ~ t = p 1 , t + H t , b ~ t = p 2 , t + H t \tilde{b}_t=p_{2,t}+H_t b ~ t = p 2 , t + H t . Taking prefix minima a ^ t = min 1 ≤ s ≤ t a ~ s \hat{a}_t=\min_{1\leq s\leq t}\tilde{a}_s a ^ t = min 1 ≤ s ≤ t a ~ s and b ^ t = min 1 ≤ r ≤ t b ~ r \hat{b}_t=\min_{1\leq r\leq t}\tilde{b}_r b ^ t = min 1 ≤ r ≤ t b ~ r reduces the full-horizon free-terminal problem and all zero-terminal prefix subproblems directly to an offline zero-holding-cost instance with non-increasing prices (a ^ t + 1 ≤ a ^ t \hat{a}_{t+1}\leq\hat{a}_t a ^ t + 1 ≤ a ^ t , b ^ t + 1 ≤ b ^ t \hat{b}_{t+1}\leq\hat{b}_t b ^ t + 1 ≤ b ^ t ). Working directly with the online effective prices ( α i , β i , h i ) (\alpha_i,\beta_i,h_i) ( α i , β i , h i ) in (6) –(7) avoids reading future holding rates h i + 1 , … , h n h_{i+1},\ldots,h_n h i + 1 , … , h n and preserves free-terminal prefix values O P T k \mathrm{OPT}_k OPT k at every intermediate period k k k as well.
A normal form under non-speculative prices
We now establish a simultaneous structural normal form for optimal schedules of the virtual model ( α i , β i , h i ) (\alpha_i,\beta_i,h_i) ( α i , β i , h i ) using only the non-speculative inequalities (9) .
Lemma 2.4 (Postponement under non-speculative prices). For all q , r ≥ 0 q,r\geq0 q , r ≥ 0 and 1 ≤ i < n 1\leq i<n 1 ≤ i < n , the virtual procurement functions (10) satisfy
P ^ i + 1 ( q ) ≤ P ^ i ( q ) + h i q and P ^ i + 1 ( q + r ) ≤ P ^ i ( q ) + h i q + P ^ i + 1 ( r ) . (18) \widehat{P}_{i+1}(q)\leq\widehat{P}_i(q)+h_iq
\qquad\text{and}\qquad
\widehat{P}_{i+1}(q+r)\leq\widehat{P}_i(q)+h_iq+\widehat{P}_{i+1}(r). \tag*{(18)} P i + 1 ( q ) ≤ P i ( q ) + h i q and P i + 1 ( q + r ) ≤ P i ( q ) + h i q + P i + 1 ( r ) . (18)
Proof. If 0 ≤ q < Q 0\leq q<Q 0 ≤ q < Q , then P ^ i + 1 ( q ) = α i + 1 q ≤ ( α i + h i ) q = P ^ i ( q ) + h i q \widehat{P}_{i+1}(q)=\alpha_{i+1}q\leq(\alpha_i+h_i)q=\widehat{P}_i(q)+h_iq P i + 1 ( q ) = α i + 1 q ≤ ( α i + h i ) q = P i ( q ) + h i q by (9) . If q ≥ Q q\geq Q q ≥ Q , then P ^ i + 1 ( q ) = β i + 1 q ≤ ( β i + h i ) q = P ^ i ( q ) + h i q \widehat{P}_{i+1}(q)=\beta_{i+1}q\leq(\beta_i+h_i)q=\widehat{P}_i(q)+h_iq P i + 1 ( q ) = β i + 1 q ≤ ( β i + h i ) q = P i ( q ) + h i q . Combining this inequality with subadditivity P ^ i + 1 ( q + r ) ≤ P ^ i + 1 ( q ) + P ^ i + 1 ( r ) \widehat{P}_{i+1}(q+r)\leq\widehat{P}_{i+1}(q)+\widehat{P}_{i+1}(r) P i + 1 ( q + r ) ≤ P i + 1 ( q ) + P i + 1 ( r ) gives the second inequality in (18) .
Lemma 2.5 (Tier-preserving trimming with holding-cost credit). Let ( q ^ , I ^ ) (\hat{q},\hat{I}) ( q ^ , I ^ ) be a feasible virtual schedule through period m ≥ 1 m\geq1 m ≥ 1 with terminal inventory w = I ^ m > 0 w=\hat{I}_m>0 w = I ^ m > 0 , and let
0 ≤ γ ≤ min 1 ≤ t ≤ m ( β t + H ( t , m + 1 ) ) . (19) 0\leq\gamma\leq\min_{1\leq t\leq m}\bigl(\beta_t+H(t,m+1)\bigr). \tag*{(19)} 0 ≤ γ ≤ 1 ≤ t ≤ m min ( β t + H ( t , m + 1 ) ) . (19)
There exists a feasible virtual schedule ( q ^ ′ , I ^ ′ ) (\hat{q}',\hat{I}') ( q ^ ′ , I ^ ′ ) through period m m m ending with inventory s = I ^ m ′ < Q s=\hat{I}'_m<Q s = I ^ m ′ < Q such that I ^ r ′ ≤ I ^ r \hat{I}'_r\leq\hat{I}_r I ^ r ′ ≤ I ^ r for every 1 ≤ r ≤ m 1\leq r\leq m 1 ≤ r ≤ m and
J ^ m ( q ^ ′ , I ^ ′ ) ≤ J ^ m ( q ^ , I ^ ) − γ ( w − s ) . (20) \hat{J}_m(\hat{q}',\hat{I}')\leq\hat{J}_m(\hat{q},\hat{I})-\gamma(w-s). \tag*{(20)} J ^ m ( q ^ ′ , I ^ ′ ) ≤ J ^ m ( q ^ , I ^ ) − γ ( w − s ) . (20)
In particular, if m = i − 1 < n m=i-1<n m = i − 1 < n , (9) implies β t + H ( t , i ) ≥ β i \beta_t+H(t,i)\geq\beta_i β t + H ( t , i ) ≥ β i for all 1 ≤ t ≤ i − 1 1\leq t\leq i-1 1 ≤ t ≤ i − 1 , so (20) holds with γ = β i \gamma=\beta_i γ = β i .
Proof. Write D r = ∑ t = 1 r d t D_r=\sum_{t=1}^{r}d_t D r = ∑ t = 1 r d t and S ^ r = ∑ t = 1 r q ^ t \hat{S}_r=\sum_{t=1}^{r}\hat{q}_t S ^ r = ∑ t = 1 r q ^ t , with D 0 = S ^ 0 = 0 D_0=\hat{S}_0=0 D 0 = S ^ 0 = 0 . Since S ^ m = D m + w > D m \hat{S}_m=D_m+w>D_m S ^ m = D m + w > D m , let j ∈ { 1 , … , m } j\in\{1,\ldots,m\} j ∈ { 1 , … , m } be the first index with S ^ j > D m \hat{S}_j>D_m S ^ j > D m , and set ℓ = D m − S ^ j − 1 ∈ [ 0 , q ^ j ) \ell=D_m-\hat{S}_{j-1}\in[0,\hat{q}_j) ℓ = D m − S ^ j − 1 ∈ [ 0 , q ^ j ) . Define ( q ^ 1 ′ , … , q ^ m ′ ) (\hat{q}'_1,\ldots,\hat{q}'_m) ( q ^ 1 ′ , … , q ^ m ′ ) by keeping q ^ t ′ = q ^ t \hat{q}'_t=\hat{q}_t q ^ t ′ = q ^ t for t < j t<j t < j , setting q ^ t ′ = 0 \hat{q}'_t=0 q ^ t ′ = 0 for t > j t>j t > j , and putting
q ^ j ′ = { ℓ , q ^ j < Q or ℓ = 0 , max { ℓ , Q } , q ^ j ≥ Q and ℓ > 0. (21) \hat{q}'_j=
\begin{cases}
\ell, & \hat{q}_j<Q\text{ or }\ell=0,\\
\max\{\ell,Q\}, & \hat{q}_j\geq Q\text{ and }\ell>0.
\end{cases} \tag*{(21)} q ^ j ′ = { ℓ , max { ℓ , Q } , q ^ j < Q or ℓ = 0 , q ^ j ≥ Q and ℓ > 0. (21)
Then q ^ ′ ∈ G m \hat{q}'\in\mathcal{G}^m q ^ ′ ∈ G m , ℓ ≤ q ^ j ′ ≤ q ^ j \ell\leq\hat{q}'_j\leq\hat{q}_j ℓ ≤ q ^ j ′ ≤ q ^ j , and s = q ^ j ′ − ℓ < Q s=\hat{q}'_j-\ell<Q s = q ^ j ′ − ℓ < Q . For r < j r<j r < j the schedule is unchanged; for j ≤ r ≤ m j\leq r\leq m j ≤ r ≤ m , S ^ r ′ = S ^ j − 1 + q ^ j ′ = D m + s ≥ D r \hat{S}'_r=\hat{S}_{j-1}+\hat{q}'_j=D_m+s\geq D_r S ^ r ′ = S ^ j − 1 + q ^ j ′ = D m + s ≥ D r and S ^ r ′ ≤ S ^ r \hat{S}'_r\leq\hat{S}_r S ^ r ′ ≤ S ^ r , so 0 ≤ I ^ r ′ ≤ I ^ r 0\leq\hat{I}'_r\leq\hat{I}_r 0 ≤ I ^ r ′ ≤ I ^ r .
Let δ t = q ^ t − q ^ t ′ ≥ 0 \delta_t=\hat{q}_t-\hat{q}'_t\geq0 δ t = q ^ t − q ^ t ′ ≥ 0 for 1 ≤ t ≤ m 1\leq t\leq m 1 ≤ t ≤ m (so δ t = 0 \delta_t=0 δ t = 0 for t < j t<j t < j and ∑ t = j m δ t = w − s \sum_{t=j}^{m}\delta_t=w-s ∑ t = j m δ t = w − s ). Because (21) leaves any positive q ^ j ′ \hat{q}'_j q ^ j ′ in the same primary tier as q ^ j \hat{q}_j q ^ j , every period t ∈ { j , … , m } t\in\{j,\ldots,m\} t ∈ { j , … , m } satisfies P ^ t ( q ^ t ) − P ^ t ( q ^ t ′ ) ≥ β t δ t \widehat{P}_t(\hat{q}_t)-\widehat{P}_t(\hat{q}'_t)\geq\beta_t\delta_t P t ( q ^ t ) − P t ( q ^ t ′ ) ≥ β t δ t . Furthermore, for every r ∈ { 1 , … , m } r\in\{1,\ldots,m\} r ∈ { 1 , … , m } , I ^ r − I ^ r ′ = S ^ r − S ^ r ′ = ∑ t = 1 r δ t \hat{I}_r-\hat{I}'_r=\hat{S}_r-\hat{S}'_r=\sum_{t=1}^{r}\delta_t I ^ r − I ^ r ′ = S ^ r − S ^ r ′ = ∑ t = 1 r δ t , so the holding-cost reduction equals
∑ r = 1 m h r ( I ^ r − I ^ r ′ ) = ∑ r = 1 m h r ∑ t = 1 r δ t = ∑ t = j m δ t ∑ r = t m h r = ∑ t = j m δ t H ( t , m + 1 ) . \sum_{r=1}^{m}h_r(\hat{I}_r-\hat{I}'_r)
=\sum_{r=1}^{m}h_r\sum_{t=1}^{r}\delta_t
=\sum_{t=j}^{m}\delta_t\sum_{r=t}^{m}h_r
=\sum_{t=j}^{m}\delta_t H(t,m+1). r = 1 ∑ m h r ( I ^ r − I ^ r ′ ) = r = 1 ∑ m h r t = 1 ∑ r δ t = t = j ∑ m δ t r = t ∑ m h r = t = j ∑ m δ t H ( t , m + 1 ) .
Adding procurement and holding savings gives
J ^ m ( q ^ , I ^ ) − J ^ m ( q ^ ′ , I ^ ′ ) ≥ ∑ t = j m δ t ( β t + H ( t , m + 1 ) ) ≥ γ ∑ t = j m δ t = γ ( w − s ) . \hat{J}_m(\hat{q},\hat{I})-\hat{J}_m(\hat{q}',\hat{I}')\ge\sum_{t=j}^{m}\delta_t\left(\beta_t+H(t,m+1)\right)\ge\gamma\sum_{t=j}^{m}\delta_t=\gamma(w-s). J ^ m ( q ^ , I ^ ) − J ^ m ( q ^ ′ , I ^ ′ ) ≥ t = j ∑ m δ t ( β t + H ( t , m + 1 ) ) ≥ γ t = j ∑ m δ t = γ ( w − s ) .
Finally, iterating β r + h r ≥ β r + 1 \beta_r+h_r\ge\beta_{r+1} β r + h r ≥ β r + 1 across r = t , … , i − 1 r=t,\ldots,i-1 r = t , … , i − 1 gives β t + H ( t , i ) ≥ β i \beta_t+H(t,i)\ge\beta_i β t + H ( t , i ) ≥ β i , proving admissibility of γ = β i \gamma=\beta_i γ = β i .
Theorem 2.6 (Simultaneous normal form for the virtual problem). For every horizon m ∈ { 1 , … , n } m\in\{1,\ldots,n\} m ∈ { 1 , … , n } , the free-terminal virtual problem admits an optimal feasible schedule ( q ^ 1 , … , q ^ m ) (\hat{q}_1,\ldots,\hat{q}_m) ( q ^ 1 , … , q ^ m ) satisfying simultaneously
q ^ i > 0 ⟹ I ^ i − 1 < d i , i = 1 , … , m , (22) \hat{q}_i>0\Longrightarrow\hat{I}_{i-1}<d_i,\qquad i=1,\ldots,m, \tag*{(22)} q ^ i > 0 ⟹ I ^ i − 1 < d i , i = 1 , … , m , (22) I ^ i − 1 < 2 Q , i = 1 , … , m , (23) \hat{I}_{i-1}<2Q,\qquad i=1,\ldots,m, \tag*{(23)} I ^ i − 1 < 2 Q , i = 1 , … , m , (23) I ^ m < Q . (24) \hat{I}_m<Q. \tag*{(24)} I ^ m < Q . (24) For the zero-terminal virtual problem ( I ^ m = 0 ) (\hat{I}_m=0) ( I ^ m = 0 ) , there exists an optimal feasible schedule satisfying (22) –(23) simultaneously on 1 , … , m 1,\ldots,m 1 , … , m .
Proof. By Lemma 2.1 applied to ( α i , β i , h i ) (\alpha_i,\beta_i,h_i) ( α i , β i , h i ) , the set of optimal virtual schedules on 1 , … , m 1,\ldots,m 1 , … , m (restricted to ∑ i = 1 m q ^ i ≤ D m + Q \sum_{i=1}^{m}\hat{q}_i\le D_m+Q ∑ i = 1 m q ^ i ≤ D m + Q in the free-terminal case, since Lemma 2.5 with γ = 0 \gamma=0 γ = 0 trims any optimal schedule with I ^ m ≥ Q \hat{I}_m\ge Q I ^ m ≥ Q without raising cost) is nonempty and compact in R ≥ 0 m \mathbb{R}_{\geq0}^{m} R ≥ 0 m (or finite in Z ≥ 0 m \mathbb{Z}_{\geq0}^{m} Z ≥ 0 m ). Among all optimal virtual schedules, choose one minimizing the linear inventory potential
Φ ( I ^ ) = ∑ t = 1 m I ^ t . (25) \Phi(\hat{I})=\sum_{t=1}^{m}\hat{I}_t. \tag*{(25)} Φ ( I ^ ) = t = 1 ∑ m I ^ t . (25) First, suppose i < m i<m i < m , I ^ i − 1 = u ≥ d i \hat{I}_{i-1}=u\ge d_i I ^ i − 1 = u ≥ d i , and q ^ i = q > 0 \hat{q}_i=q>0 q ^ i = q > 0 . Set r = q ^ i + 1 r=\hat{q}_{i+1} r = q ^ i + 1 and replace ( q ^ i , q ^ i + 1 ) (\hat{q}_i,\hat{q}_{i+1}) ( q ^ i , q ^ i + 1 ) by ( 0 , q + r ) (0,q+r) ( 0 , q + r ) . Then I ^ i ′ = u − d i = I ^ i − q ≥ 0 \hat{I}'_i=u-d_i=\hat{I}_i-q\ge0 I ^ i ′ = u − d i = I ^ i − q ≥ 0 , while I ^ i ′ + ( q + r ) = I ^ i + r \hat{I}'_i+(q+r)=\hat{I}_i+r I ^ i ′ + ( q + r ) = I ^ i + r leaves I ^ i + 1 , … , I ^ m \hat{I}_{i+1},\ldots,\hat{I}_m I ^ i + 1 , … , I ^ m unchanged. By Lemma 2.4, total procurement plus period-i i i holding cost changes by P ^ i + 1 ( q + r ) − P ^ i ( q ) − P ^ i + 1 ( r ) − h i q ≤ 0 \hat{P}_{i+1}(q+r)-\hat{P}_i(q)-\hat{P}_{i+1}(r)-h_iq\le0 P ^ i + 1 ( q + r ) − P ^ i ( q ) − P ^ i + 1 ( r ) − h i q ≤ 0 , whereas Φ ( I ^ ) \Phi(\hat{I}) Φ ( I ^ ) strictly decreases by q > 0 q>0 q > 0 , contradicting minimality of Φ \Phi Φ . At i = m i=m i = m , I ^ m − 1 ≥ d m \hat{I}_{m-1}\ge d_m I ^ m − 1 ≥ d m and q ^ m > 0 \hat{q}_m>0 q ^ m > 0 is impossible when I ^ m = 0 \hat{I}_m=0 I ^ m = 0 , and in the free-terminal case setting q ^ m = 0 \hat{q}_m=0 q ^ m = 0 preserves I ^ m ′ ≥ 0 \hat{I}'_m\ge0 I ^ m ′ ≥ 0 , lowers cost weakly, and strictly decreases Φ \Phi Φ . Thus (22) holds.
Second, suppose w = I ^ i − 1 ≥ 2 Q w=\hat{I}_{i-1}\ge2Q w = I ^ i − 1 ≥ 2 Q for some 2 ≤ i ≤ m 2\le i\le m 2 ≤ i ≤ m . Apply Lemma 2.5 through period i − 1 i-1 i − 1 with γ = β i \gamma=\beta_i γ = β i to obtain ( q ^ 1 ′ , … , q ^ i − 1 ′ ) (\hat{q}'_1,\ldots,\hat{q}'_{i-1}) ( q ^ 1 ′ , … , q ^ i − 1 ′ ) ending at s = I ^ i − 1 ′ < Q s=\hat{I}'_{i-1}<Q s = I ^ i − 1 ′ < Q with J ^ i − 1 ( q ^ ′ ) ≤ J ^ i − 1 ( q ^ , I ^ ) − β i ( w − s ) \hat{J}_{i-1}(\hat{q}')\le\hat{J}_{i-1}(\hat{q},\hat{I})-\beta_i(w-s) J ^ i − 1 ( q ^ ′ ) ≤ J ^ i − 1 ( q ^ , I ^ ) − β i ( w − s ) . Set q ^ i ′ = q ^ i + w − s \hat{q}'_i=\hat{q}_i+w-s q ^ i ′ = q ^ i + w − s and keep q ^ t ′ = q ^ t \hat{q}'_t=\hat{q}_t q ^ t ′ = q ^ t for t > i t>i t > i . Because w ≥ 2 Q w\ge2Q w ≥ 2 Q and s < Q s<Q s < Q , we have q ^ i ′ > Q \hat{q}'_i>Q q ^ i ′ > Q , so P ^ i ( q ^ i ′ ) − P ^ i ( q ^ i ) = β i ( q ^ i + w − s ) − P ^ i ( q ^ i ) ≤ β i ( w − s ) \hat{P}_i(\hat{q}'_i)-\hat{P}_i(\hat{q}_i)=\beta_i(\hat{q}_i+w-s)-\hat{P}_i(\hat{q}_i)\le\beta_i(w-s) P ^ i ( q ^ i ′ ) − P ^ i ( q ^ i ) = β i ( q ^ i + w − s ) − P ^ i ( q ^ i ) ≤ β i ( w − s ) . Since s + q ^ i ′ = w + q ^ i s+\hat{q}'_i=w+\hat{q}_i s + q ^ i ′ = w + q ^ i , inventories from period i i i onward are identical, earlier inventories weakly decrease, and I ^ i − 1 ′ = s < w \hat{I}'_{i-1}=s<w I ^ i − 1 ′ = s < w strictly decreases Φ ( I ^ ) \Phi(\hat{I}) Φ ( I ^ ) without increasing total cost—a contradiction. Since I ^ 0 = 0 \hat{I}_0=0 I ^ 0 = 0 , (23) holds for all i i i .
Third, in the free-terminal case, I ^ m ≥ Q \hat{I}_m\ge Q I ^ m ≥ Q is ruled out by applying Lemma 2.5 on 1 , … , m 1,\ldots,m 1 , … , m with γ = 0 \gamma=0 γ = 0 , which yields I ^ m ′ < Q \hat{I}'_m<Q I ^ m ′ < Q and strictly smaller Φ \Phi Φ . Because every contradiction is derived against the same minimizer of Φ \Phi Φ , (22) –(24) hold simultaneously.
The auxiliary dynamic program and single-crossover property
Define the bounded state and departure domains
K 1 = 0 , K i + 1 = 2 Q , Y i = d i + 2 Q , i = 1 , … , n . (26) K_1=0,\qquad K_{i+1}=2Q,\qquad Y_i=d_i+2Q,\qquad i=1,\ldots,n. \tag*{(26)} K 1 = 0 , K i + 1 = 2 Q , Y i = d i + 2 Q , i = 1 , … , n . (26)
The incoming auxiliary value function A i A_i A i is supported on [ 0 , K i ] ∩ G [0,K_i]\cap\mathcal{G} [ 0 , K i ] ∩ G (extended by + ∞ +\infty + ∞ elsewhere), initialized by A 1 ( 0 ) = 0 A_1(0)=0 A 1 ( 0 ) = 0 . For i = 1 , … , n i=1,\ldots,n i = 1 , … , n and y ∈ [ 0 , Y i ] ∩ G y\in[0,Y_i]\cap\mathcal{G} y ∈ [ 0 , Y i ] ∩ G , define
O i ( y ) = inf 0 ≤ u ≤ y { A i ( u ) + α i ( y − u ) } , (27) O_i(y)=\inf_{0\leq u\leq y}\left\{A_i(u)+\alpha_i(y-u)\right\}, \tag*{(27)} O i ( y ) = 0 ≤ u ≤ y inf { A i ( u ) + α i ( y − u ) } , (27)
N i ( y ) = inf 0 ≤ u < d i u + Q ≤ y { A i ( u ) + β i ( y − u ) } , (28) N_i(y)=\inf_{\substack{0\leq u<d_i\\u+Q\leq y}}\left\{A_i(u)+\beta_i(y-u)\right\}, \tag*{(28)} N i ( y ) = 0 ≤ u < d i u + Q ≤ y inf { A i ( u ) + β i ( y − u ) } , (28)
F i ( y ) = min { O i ( y ) , N i ( y ) } , (29) F_i(y)=\min\{O_i(y),N_i(y)\}, \tag*{(29)} F i ( y ) = min { O i ( y ) , N i ( y )} , (29)
A i + 1 ( z ) = F i ( d i + z ) + h i z , z ∈ [ 0 , K i + 1 ] ∩ G , (30) A_{i+1}(z)=F_i(d_i+z)+h_i z,\qquad z\in[0,K_{i+1}]\cap\mathcal{G}, \tag*{(30)} A i + 1 ( z ) = F i ( d i + z ) + h i z , z ∈ [ 0 , K i + 1 ] ∩ G , (30)
where inf ∅ = + ∞ \inf\varnothing=+\infty inf ∅ = + ∞ and predecessor variables u u u range over G \mathcal{G} G . In this auxiliary model, a regular action may purchase any quantity y − u ≥ 0 y-u\geq0 y − u ≥ 0 at unit rate α i \alpha_i α i (even if y − u ≥ Q y-u\geq Q y − u ≥ Q ), whereas a discounted action pays β i \beta_i β i per unit, requires y − u ≥ Q y-u\geq Q y − u ≥ Q , and is permitted only when u < d i u<d_i u < d i .
Theorem 2.7 (Exactness of the auxiliary dynamic program). For every prefix k ∈ { 1 , … , n } k\in\{1,\ldots,n\} k ∈ { 1 , … , n } , the auxiliary recurrence (2.27)–(2.30) satisfies
A k + 1 ( 0 ) = O P T ^ k , 0 and min 0 ≤ z ≤ K k + 1 A k + 1 ( z ) = O P T ^ k , (31) A_{k+1}(0)=\widehat{\mathrm{OPT}}_{k,0}
\qquad\text{and}\qquad
\min_{0\leq z\leq K_{k+1}}A_{k+1}(z)=\widehat{\mathrm{OPT}}_k, \tag*{(31)} A k + 1 ( 0 ) = OPT k , 0 and 0 ≤ z ≤ K k + 1 min A k + 1 ( z ) = OPT k , (31) with the second minimum attained at some z < Q z<Q z < Q . In particular, min 0 ≤ z ≤ 2 Q A n + 1 ( z ) = O P T \min_{0\leq z\leq2Q}A_{n+1}(z)=\mathrm{OPT} min 0 ≤ z ≤ 2 Q A n + 1 ( z ) = OPT .
Proof. By Theorem 2.2, it suffices to compare A k + 1 A_{k+1} A k + 1 with O P T ^ k , 0 \widehat{\mathrm{OPT}}_{k,0} OPT k , 0 and O P T ^ k \widehat{\mathrm{OPT}}_k OPT k . Every auxiliary trajectory through period k k k defines a feasible virtual schedule ( q ^ 1 , … , q ^ k ) (\widehat{q}_1,\ldots,\widehat{q}_k) ( q 1 , … , q k ) whose auxiliary procurement charges satisfy α i q ^ i ≥ P ^ i ( q ^ i ) \alpha_i\widehat{q}_i\geq\widehat{P}_i(\widehat{q}_i) α i q i ≥ P i ( q i ) on regular steps and β i q ^ i = P ^ i ( q ^ i ) \beta_i\widehat{q}_i=\widehat{P}_i(\widehat{q}_i) β i q i = P i ( q i ) on discounted steps (where q ^ i ≥ Q \widehat{q}_i\geq Q q i ≥ Q ). Thus A k + 1 ( 0 ) ≥ O P T ^ k , 0 A_{k+1}(0)\geq\widehat{\mathrm{OPT}}_{k,0} A k + 1 ( 0 ) ≥ OPT k , 0 and inf 0 ≤ z ≤ 2 Q A k + 1 ( z ) ≥ O P T ^ k \inf_{0\leq z\leq2Q}A_{k+1}(z)\geq\widehat{\mathrm{OPT}}_k inf 0 ≤ z ≤ 2 Q A k + 1 ( z ) ≥ OPT k .
Conversely, let ( q ^ 1 , … , q ^ k ) (\widehat{q}_1,\ldots,\widehat{q}_k) ( q 1 , … , q k ) be the optimal virtual schedule given by Theorem 2.6 for prefix k k k under either terminal convention. Every step with 0 ≤ q ^ i < Q 0\leq\widehat{q}_i<Q 0 ≤ q i < Q uses the regular operator (2.27) at exact cost P ^ i ( q ^ i ) = α i q ^ i \widehat{P}_i(\widehat{q}_i)=\alpha_i\widehat{q}_i P i ( q i ) = α i q i ; every step with q ^ i ≥ Q \widehat{q}_i\geq Q q i ≥ Q has I ^ i − 1 < d i \widehat{I}_{i-1}<d_i I i − 1 < d i by (2.22) and uses the discounted operator (2.28) at exact cost P ^ i ( q ^ i ) = β i q ^ i \widehat{P}_i(\widehat{q}_i)=\beta_i\widehat{q}_i P i ( q i ) = β i q i . Moreover, I ^ i − 1 < 2 Q \widehat{I}_{i-1}<2Q I i − 1 < 2 Q for all 1 ≤ i ≤ k 1\leq i\leq k 1 ≤ i ≤ k and I ^ k < Q \widehat{I}_k<Q I k < Q (or I ^ k = 0 \widehat{I}_k=0 I k = 0 ), so every visited state lies strictly inside [ 0 , K i ] [0,K_i] [ 0 , K i ] and every departure level I ^ i − 1 + q ^ i = d i + I ^ i \widehat{I}_{i-1}+\widehat{q}_i=d_i+\widehat{I}_i I i − 1 + q i = d i + I i lies inside [ 0 , Y i ] [0,Y_i] [ 0 , Y i ] . Hence the auxiliary recurrence evaluates this schedule at exact cost O P T ^ k \widehat{\mathrm{OPT}}_k OPT k (or O P T ^ k , 0 \widehat{\mathrm{OPT}}_{k,0} OPT k , 0 ), proving equality and attainment below Q Q Q . □
For an operator notation on a function C C C extended by + ∞ +\infty + ∞ outside its domain, write ( O a C ) ( y ) = inf 0 ≤ u ≤ y { C ( u ) + a ( y − u ) } (O_aC)(y)=\inf_{0\leq u\leq y}\{C(u)+a(y-u)\} ( O a C ) ( y ) = inf 0 ≤ u ≤ y { C ( u ) + a ( y − u )} and ( D b , d C ) ( y ) = inf 0 ≤ u < d u + Q ≤ y { C ( u ) + b ( y − u ) } (D_{b,d}C)(y)=\inf_{\substack{0\leq u<d\\u+Q\leq y}}\{C(u)+b(y-u)\} ( D b , d C ) ( y ) = inf 0 ≤ u < d u + Q ≤ y { C ( u ) + b ( y − u )} .
Lemma 2.8 (Closure and distributivity). For any a ≥ b ≥ 0 a\geq b\geq0 a ≥ b ≥ 0 and Y ≥ d ≥ 0 Y\geq d\geq0 Y ≥ d ≥ 0 , restricted to y ∈ [ 0 , Y ] ∩ G y\in[0,Y]\cap\mathcal{G} y ∈ [ 0 , Y ] ∩ G ,
O a O a C = O a C , D b , d O a C = D b , d C , O a D b , d C = D b , d C , (32) O_aO_aC=O_aC,\qquad D_{b,d}O_aC=D_{b,d}C,\qquad O_aD_{b,d}C=D_{b,d}C, \tag*{(32)} O a O a C = O a C , D b , d O a C = D b , d C , O a D b , d C = D b , d C , (32) and both operators distribute over pointwise infima. Consequently, F = min { O a C , D b , d C } F=\min\{O_aC,D_{b,d}C\} F = min { O a C , D b , d C } satisfies O a F = F O_aF=F O a F = F .
Proof. For O a O a C O_aO_aC O a O a C , C ( v ) + a ( u − v ) + a ( y − u ) = C ( v ) + a ( y − v ) C(v)+a(u-v)+a(y-u)=C(v)+a(y-v) C ( v ) + a ( u − v ) + a ( y − u ) = C ( v ) + a ( y − v ) for v ≤ u ≤ y v\leq u\leq y v ≤ u ≤ y . For D b , d O a C D_{b,d}O_aC D b , d O a C , any v ≤ u < d v\leq u<d v ≤ u < d with u + Q ≤ y u+Q\leq y u + Q ≤ y satisfies v < d v<d v < d , v + Q ≤ y v+Q\leq y v + Q ≤ y , and C ( v ) + a ( u − v ) + b ( y − u ) = C ( v ) + b ( y − v ) + ( a − b ) ( u − v ) ≥ C ( v ) + b ( y − v ) C(v)+a(u-v)+b(y-u)=C(v)+b(y-v)+(a-b)(u-v)\geq C(v)+b(y-v) C ( v ) + a ( u − v ) + b ( y − u ) = C ( v ) + b ( y − v ) + ( a − b ) ( u − v ) ≥ C ( v ) + b ( y − v ) , with equality at u = v u=v u = v . For O a D b , d C O_aD_{b,d}C O a D b , d C , any u < d u<d u < d with u + Q ≤ v ≤ y u+Q\leq v\leq y u + Q ≤ v ≤ y satisfies C ( u ) + b ( v − u ) + a ( y − v ) = C ( u ) + b ( y − u ) + ( a − b ) ( y − v ) ≥ C ( u ) + b ( y − u ) C(u)+b(v-u)+a(y-v)=C(u)+b(y-u)+(a-b)(y-v)\geq C(u)+b(y-u) C ( u ) + b ( v − u ) + a ( y − v ) = C ( u ) + b ( y − u ) + ( a − b ) ( y − v ) ≥ C ( u ) + b ( y − u ) , with equality at v = y v=y v = y . All intermediate states lie in [ 0 , Y ] [0,Y] [ 0 , Y ] when y ≤ Y y\leq Y y ≤ Y and Y ≥ d Y\geq d Y ≥ d . Distributivity over pointwise infima gives O a F = F O_aF=F O a F = F . □
Proposition 2.9 (Piecewise-affine slopes and attainment). For each period i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } , A i A_i A i , O i O_i O i , N i N_i N i , and F i F_i F i have finite piecewise-affine descriptions on their finite domains, every affine piece has slope at least β i \beta_i β i , and every finite infimum in (2.27)–(2.28) is attained. In the continuous model G = R ≥ 0 \mathcal{G}=\mathbb{R}_{\geq0} G = R ≥ 0 , the functions are right-continuous on the interior of their finite domains with no upward jumps.
Proof. At i = 1 i=1 i = 1 , A 1 A_1 A 1 is supported on { 0 } \{0\} { 0 } , O 1 ( y ) = α 1 y O_1(y)=\alpha_1y O 1 ( y ) = α 1 y has slope α 1 ≥ β 1 \alpha_1\ge\beta_1 α 1 ≥ β 1 , and N 1 ( y ) = β 1 y N_1(y)=\beta_1y N 1 ( y ) = β 1 y (for d 1 > 0 d_1>0 d 1 > 0 , y ≥ Q y\ge Q y ≥ Q ) has slope β 1 \beta_1 β 1 . Suppose the claim holds for A i A_i A i . Since every piece of A i A_i A i has slope p ≥ β i p\ge\beta_i p ≥ β i , O α i A i O_{\alpha_i}A_i O α i A i produces pieces of slope min { p , α i } ≥ β i \min\{p,\alpha_i\}\ge\beta_i min { p , α i } ≥ β i . Within each piece of A i A_i A i , u ↦ A i ( u ) − β i u u\mapsto A_i(u)-\beta_i u u ↦ A i ( u ) − β i u is nondecreasing, so its infimum over 0 ≤ u < d i 0\le u<d_i 0 ≤ u < d i , u ≤ y − Q u\le y-Q u ≤ y − Q is attained at one of finitely many left endpoints of pieces of A i A_i A i strictly below d i d_i d i (never requiring an unattained open right endpoint d i d_i d i ). Thus N i N_i N i is piecewise affine of slope β i \beta_i β i with finitely many downward jumps, and F i = min { O i , N i } F_i=\min\{O_i,N_i\} F i = min { O i , N i } preserves slopes ≥ β i \ge\beta_i ≥ β i , right-continuity, and lower semicontinuity. Finally, A i + 1 ( z ) = F i ( d i + z ) + h i z A_{i+1}(z)=F_i(d_i+z)+h_i z A i + 1 ( z ) = F i ( d i + z ) + h i z shifts all slopes by + h i +h_i + h i , so every piece of A i + 1 A_{i+1} A i + 1 has slope at least β i + h i ≥ β i + 1 \beta_i+h_i\ge\beta_{i+1} β i + h i ≥ β i + 1 by (9) .
Proposition 2.10 (Normalized high-inventory invariant). For every period $i\in{1,\ldots,n}:
u ↦ A i ( u ) − β i u u\mapsto A_i(u)-\beta_i u u ↦ A i ( u ) − β i u is nondecreasing on [ Q , K i ] ∩ G [Q,K_i]\cap\mathcal{G} [ Q , K i ] ∩ G ;
y ↦ O i ( y ) − β i y y\mapsto O_i(y)-\beta_i y y ↦ O i ( y ) − β i y is nondecreasing on [ Q , Y i ] ∩ G [Q,Y_i]\cap\mathcal{G} [ Q , Y i ] ∩ G ;
y ↦ N i ( y ) − β i y y\mapsto N_i(y)-\beta_i y y ↦ N i ( y ) − β i y is nonincreasing on [ Q , Y i ] ∩ G [Q,Y_i]\cap\mathcal{G} [ Q , Y i ] ∩ G (with + ∞ +\infty + ∞ allowed prior to activation).
Proof. Claim 3 holds directly from N i ( y ) − β i y = inf 0 ≤ u < d i , u ≤ y − Q { A i ( u ) − β i u } N_i(y)-\beta_i y=\inf_{0\le u<d_i,\ u\le y-Q}\{A_i(u)-\beta_i u\} N i ( y ) − β i y = inf 0 ≤ u < d i , u ≤ y − Q { A i ( u ) − β i u } , whose feasible set expands with y y y . Next, suppose Claim 1 holds at period i i i and fix Q ≤ x < y ≤ Y i Q\le x<y\le Y_i Q ≤ x < y ≤ Y i . For any finite predecessor u ≤ y u\le y u ≤ y in O i ( y ) O_i(y) O i ( y ) : if u ≤ x u\le x u ≤ x , then A i ( u ) + α i ( y − u ) − β i y = A i ( u ) + α i ( x − u ) − β i x + ( α i − β i ) ( y − x ) ≥ O i ( x ) − β i x A_i(u)+\alpha_i(y-u)-\beta_i y=A_i(u)+\alpha_i(x-u)-\beta_i x+(\alpha_i-\beta_i)(y-x)\ge O_i(x)-\beta_i x A i ( u ) + α i ( y − u ) − β i y = A i ( u ) + α i ( x − u ) − β i x + ( α i − β i ) ( y − x ) ≥ O i ( x ) − β i x ; if u > x ≥ Q u>x\ge Q u > x ≥ Q , Claim 1 gives A i ( u ) − β i u ≥ A i ( x ) − β i x ≥ O i ( x ) − β i x A_i(u)-\beta_i u\ge A_i(x)-\beta_i x\ge O_i(x)-\beta_i x A i ( u ) − β i u ≥ A i ( x ) − β i x ≥ O i ( x ) − β i x , and adding ( α i − β i ) ( y − u ) ≥ 0 (\alpha_i-\beta_i)(y-u)\ge0 ( α i − β i ) ( y − u ) ≥ 0 yields the same lower bound. Taking the infimum over u u u proves Claim 2.
We prove Claim 1 by induction on i i i . At i = 1 i=1 i = 1 , [ Q , K 1 ] = [ Q , 0 ] = ∅ [Q,K_1]=[Q,0]=\varnothing [ Q , K 1 ] = [ Q , 0 ] = ∅ , so Claim 1 is vacuous. Assuming Claim 1 at period i i i , Claim 2 holds at period i i i . For every z ∈ [ Q , K i + 1 ] ∩ G z\in[Q,K_{i+1}]\cap\mathcal{G} z ∈ [ Q , K i + 1 ] ∩ G , the target y = d i + z y=d_i+z y = d i + z satisfies y − Q = d i + ( z − Q ) ≥ d i y-Q=d_i+(z-Q)\ge d_i y − Q = d i + ( z − Q ) ≥ d i , which activates every predecessor u < d i u<d_i u < d i simultaneously. Writing M i = inf 0 ≤ u < d i { A i ( u ) − β i u } ∈ ( − ∞ , + ∞ ] M_i=\inf_{0\le u<d_i}\{A_i(u)-\beta_i u\}\in(-\infty,+\infty] M i = inf 0 ≤ u < d i { A i ( u ) − β i u } ∈ ( − ∞ , + ∞ ] , we obtain for i < n i<n i < n :
A i + 1 ( z ) − β i + 1 z = min { O i ( d i + z ) − β i ( d i + z ) , M i } + β i d i + ( β i + h i − β i + 1 ) z . (33) A_{i+1}(z)-\beta_{i+1}z=\min\{O_i(d_i+z)-\beta_i(d_i+z),M_i\}+\beta_i d_i+(\beta_i+h_i-\beta_{i+1})z. \tag*{(33)} A i + 1 ( z ) − β i + 1 z = min { O i ( d i + z ) − β i ( d i + z ) , M i } + β i d i + ( β i + h i − β i + 1 ) z . (33)
By Claim 2, z ↦ O i ( d i + z ) − β i ( d i + z ) z\mapsto O_i(d_i+z)-\beta_i(d_i+z) z ↦ O i ( d i + z ) − β i ( d i + z ) is nondecreasing for z ≥ Q z\ge Q z ≥ Q ; taking its pointwise minimum with the constant M i M_i M i preserves monotonicity; and ( β i + h i − β i + 1 ) z (\beta_i+h_i-\beta_{i+1})z ( β i + h i − β i + 1 ) z is nondecreasing by the non-speculative inequality β i + 1 ≤ β i + h i \beta_{i+1}\le\beta_i+h_i β i + 1 ≤ β i + h i in (9) . This completes the induction.
Theorem 2.11 (Single-crossover property). For every period i i i and all Q ≤ x ≤ y ≤ Y i Q\le x\le y\le Y_i Q ≤ x ≤ y ≤ Y i in G \mathcal{G} G ,
N i ( x ) ≤ O i ( x ) ⟹ N i ( y ) ≤ O i ( y ) , (34) N_i(x)\le O_i(x)\Longrightarrow N_i(y)\le O_i(y), \tag*{(34)} N i ( x ) ≤ O i ( x ) ⟹ N i ( y ) ≤ O i ( y ) , (34) and if N i ( x ) < O i ( x ) N_i(x)<O_i(x) N i ( x ) < O i ( x ) , then N i ( y ) < O i ( y ) N_i(y)<O_i(y) N i ( y ) < O i ( y ) . Assigning ties to N i N_i N i makes the winning region of N i N_i N i on [ max { Q , d i } , Y i ] [\max\{Q,d_i\},Y_i] [ max { Q , d i } , Y i ] a contiguous suffix.
Proof. Notice that O i O_i O i is finite throughout [ 0 , Y i ] [0,Y_i] [ 0 , Y i ] because A i ( 0 ) A_i(0) A i ( 0 ) is finite. If N i ( x ) ≤ O i ( x ) N_i(x)\le O_i(x) N i ( x ) ≤ O i ( x ) , then N i ( x ) < + ∞ N_i(x)<+\infty N i ( x ) < + ∞ , and Proposition 2.10 gives
N i ( y ) − β i y ≤ N i ( x ) − β i x ≤ O i ( x ) − β i x ≤ O i ( y ) − β i y , N_i(y)-\beta_i y\le N_i(x)-\beta_i x\le O_i(x)-\beta_i x\le O_i(y)-\beta_i y, N i ( y ) − β i y ≤ N i ( x ) − β i x ≤ O i ( x ) − β i x ≤ O i ( y ) − β i y ,
with strictness preserved when the middle inequality is strict.
Normalized Candidates and Certified Frontier Operations
To maintain A i A_i A i , O i O_i O i , N i N_i N i , and F i F_i F i without enumerating quantities up to Q Q Q or d i d_i d i , we represent each frontier as the lower envelope of ordered one-kink candidate functions. Throughout, write x + = max { x , 0 } x_+=\max\{x,0\} x + = max { x , 0 } .
Normal-form candidate families
Definition 3.1 (Normalized candidate family). Fix a common regular comparator price c ≥ 0 c \ge0 c ≥ 0 and a domain bound U ∈ G U \in\mathcal{G} U ∈ G . A candidate j j j is a tuple ( f j , v j , π j , t j ) (f_j,v_j,\pi_j,t_j) ( f j , v j , π j , t j ) with anchor f j ∈ G f_j \in\mathcal{G} f j ∈ G , finite anchor value v j ∈ R v_j \in\mathbb{R} v j ∈ R , legacy slope label π j ∈ [ 0 , + ∞ ] \pi_j \in[0,+\infty] π j ∈ [ 0 , + ∞ ] (with min { + ∞ , c } = c \min\{+\infty,c\}=c min { + ∞ , c } = c ), and legacy endpoint t j ∈ G t_j \in\mathcal{G} t j ∈ G , defining the curve
E j ( x ; c ) = { + ∞ , x < f j , v j + min { π j , c } min { x − f j , t j − f j } + c ( x − t j ) + , x ≥ f j . (35) E_j(x;c)=
\begin{cases}
+\infty, & x<f_j,\\
v_j+\min\{\pi_j,c\}\min\{x-f_j,t_j-f_j\}+c(x-t_j)_+, & x\ge f_j.
\end{cases} \tag*{(35)} E j ( x ; c ) = { + ∞ , v j + min { π j , c } min { x − f j , t j − f j } + c ( x − t j ) + , x < f j , x ≥ f j . (35) A nonempty family of m m m candidates represents C ( x ) = min 1 ≤ j ≤ m E j ( x ; c ) C(x)=\min_{1\le j\le m}E_j(x;c) C ( x ) = min 1 ≤ j ≤ m E j ( x ; c ) on [ 0 , U ] ∩ G [0,U]\cap\mathcal{G} [ 0 , U ] ∩ G (and + ∞ +\infty + ∞ outside; the empty family represents + ∞ +\infty + ∞ everywhere) and is in normal form if
0 ≤ f j ≤ t j ≤ f j + 1 ( 1 ≤ j < m ) , f m ≤ t m ≤ U , π 1 ≥ π 2 ≥ ⋯ ≥ π m , (36) 0\le f_j\le t_j\le f_{j+1}\quad(1\le j<m),\qquad f_m\le t_m\le U,\qquad\pi_1\ge\pi_2\ge\cdots\ge\pi_m, \tag*{(36)} 0 ≤ f j ≤ t j ≤ f j + 1 ( 1 ≤ j < m ) , f m ≤ t m ≤ U , π 1 ≥ π 2 ≥ ⋯ ≥ π m , (36) coincident pure-linear candidates ( f j = t j = f j + 1 = t j + 1 ) (f_j=t_j=f_{j+1}=t_{j+1}) ( f j = t j = f j + 1 = t j + 1 ) are coalesced to retain a single minimum-value candidate, and the pruned prefix-certificate condition holds:
E j − 1 ( t j ; c ) > E j ( t j ; c ) , j = 2 , … , m . (37) E_{j-1}(t_j;c)>E_j(t_j;c),\qquad j=2,\ldots,m. \tag*{(37)} E j − 1 ( t j ; c ) > E j ( t j ; c ) , j = 2 , … , m . (37) Coalescing identical pure-linear candidates ensures that the lexicographic pairs ( t j , f j ) (t_j,f_j) ( t j , f j ) are strictly increasing with j j j . In the continuous model, if candidate j + 1 j+1 j + 1 introduces a downward jump at f j + 1 = t j f_{j+1}=t_j f j + 1 = t j , evaluation of (3.3) at t j t_j t j compares the continuous formulas directly, while point queries evaluate both neighbors so the jump at f j + 1 f_{j+1} f j + 1 is respected.
Lemma 3.2 (Checkpoint domination and two-neighbor queries). In any family satisfying (3.2):
For j < k j<k j < k , x ↦ E j ( x ; c ) − E k ( x ; c ) x\mapsto E_j(x;c)-E_k(x;c) x ↦ E j ( x ; c ) − E k ( x ; c ) is nondecreasing on [ f k , t k ] [f_k,t_k] [ f k , t k ] and constant on [ t k , + ∞ ) [t_k,+\infty) [ t k , + ∞ ) . Hence E j ( t k ; c ) ≤ E k ( t k ; c ) E_j(t_k;c)\le E_k(t_k;c) E j ( t k ; c ) ≤ E k ( t k ; c ) if and only if E j ( x ; c ) ≤ E k ( x ; c ) E_j(x;c)\le E_k(x;c) E j ( x ; c ) ≤ E k ( x ; c ) for all x ≥ f k x\ge f_k x ≥ f k .
If (3.3) holds, then E h ( x ; c ) > E j ( x ; c ) E_h(x;c)>E_j(x;c) E h ( x ; c ) > E j ( x ; c ) for every h < j h<j h < j and every x ≥ t j x\ge t_j x ≥ t j .
Consequently, for any pruned nonempty family and x ∈ [ 0 , U ] ∩ G x\in[0,U]\cap\mathcal{G} x ∈ [ 0 , U ] ∩ G , let j j j be the largest index with t j ≤ x t_j\le x t j ≤ x . If no such j j j exists, C ( x ) = E 1 ( x ; c ) C(x)=E_1(x;c) C ( x ) = E 1 ( x ; c ) ; if j = m j=m j = m , C ( x ) = E m ( x ; c ) C(x)=E_m(x;c) C ( x ) = E m ( x ; c ) ; and if 1 ≤ j < m 1\le j<m 1 ≤ j < m ,
C ( x ) = min { E j ( x ; c ) , E j + 1 ( x ; c ) } . (38) C(x)=\min\{E_j(x;c),E_{j+1}(x;c)\}. \tag*{(38)} C ( x ) = min { E j ( x ; c ) , E j + 1 ( x ; c )} . (38)
Proof. For j < k j<k j < k and x ≥ f k ≥ t j x\ge f_k\ge t_j x ≥ f k ≥ t j , E j ( x ; c ) E_j(x;c) E j ( x ; c ) has slope c c c , whereas E k ( x ; c ) E_k(x;c) E k ( x ; c ) has slope min { π k , c } ≤ c \min\{\pi_k,c\}\le c min { π k , c } ≤ c on [ f k , t k ] [f_k,t_k] [ f k , t k ] and slope c c c on [ t k , + ∞ ) [t_k,+\infty) [ t k , + ∞ ) (and even if f k = t j f_k=t_j f k = t j , no earlier interval exists in [ f k , + ∞ ) [f_k,+\infty) [ f k , + ∞ ) ). Thus E j − E k E_j-E_k E j − E k attains its maximum over [ f k , + ∞ ) [f_k,+\infty) [ f k , + ∞ ) at t k t_k t k , proving Claim 1. For Claim 2, for every ℓ < j \ell<j ℓ < j and x ≥ t j ≥ t ℓ + 1 x\ge t_j\ge t_{\ell+1} x ≥ t j ≥ t ℓ + 1 , E ℓ ( x ; c ) − E ℓ + 1 ( x ; c ) = E ℓ ( t ℓ + 1 ; c ) − E ℓ + 1 ( t ℓ + 1 ; c ) > 0 E_\ell(x;c)-E_{\ell+1}(x;c)=E_\ell(t_{\ell+1};c)-E_{\ell+1}(t_{\ell+1};c)>0 E ℓ ( x ; c ) − E ℓ + 1 ( x ; c ) = E ℓ ( t ℓ + 1 ; c ) − E ℓ + 1 ( t ℓ + 1 ; c ) > 0 ; summing over ℓ = h , … , j − 1 \ell=h,\ldots,j-1 ℓ = h , … , j − 1 gives E h ( x ; c ) > E j ( x ; c ) E_h(x;c)>E_j(x;c) E h ( x ; c ) > E j ( x ; c ) . For Claim 3, Claim 2 eliminates all h < j h<j h < j at x ≥ t j x\ge t_j x ≥ t j , while t j + 1 > x t_{j+1}>x t j + 1 > x implies f k ≥ t k − 1 ≥ t j + 1 > x f_k\ge t_{k-1}\ge t_{j+1}>x f k ≥ t k − 1 ≥ t j + 1 > x for all k ≥ j + 2 k\ge j+2 k ≥ j + 2 , making those candidates + ∞ +\infty + ∞ at x x x .
Regular closure and exact three-regime comparator thresholds
Lemma 3.3 (Regular closure via comparator lowering). Let C C C be represented on [ 0 , U ] [0,U] [ 0 , U ] at comparator c c c , and let 0 ≤ a ≤ c 0\le a\le c 0 ≤ a ≤ c . For every y ≥ 0 y\ge0 y ≥ 0 in G \mathcal{G} G ,
inf 0 ≤ u ≤ min { y , U } { C ( u ) + a ( y − u ) } = min 1 ≤ j ≤ m E j ( y ; a ) . (39) \inf_{0\le u\le\min\{y,U\}}\{C(u)+a(y-u)\}=\min_{1\le j\le m}E_j(y;a). \tag*{(39)} 0 ≤ u ≤ m i n { y , U } inf { C ( u ) + a ( y − u )} = 1 ≤ j ≤ m min E j ( y ; a ) . (39)
Proof. Distribute the infimum over j = 1 , … , m j=1,\ldots,m j = 1 , … , m . Fix j j j and put s = min { π j , c } s=\min\{\pi_j,c\} s = min { π j , c } . On [ f j , U ] [f_j,U] [ f j , U ] , u ↦ E j ( u ; c ) − a u u\mapsto E_j(u;c)-au u ↦ E j ( u ; c ) − a u has slope s − a s-a s − a on [ f j , t j ] [f_j,t_j] [ f j , t j ] and slope c − a ≥ 0 c-a\ge0 c − a ≥ 0 on [ t j , U ] [t_j,U] [ t j , U ] . For y ≥ f j y\ge f_j y ≥ f j , its minimum over u ∈ [ f j , min { y , U } ] u\in[f_j,\min\{y,U\}] u ∈ [ f j , min { y , U }] is attained at u = f j ∈ G u=f_j\in\mathcal{G} u = f j ∈ G if s ≥ a s\ge a s ≥ a , and at u = min { y , t j } ∈ G u=\min\{y,t_j\}\in\mathcal{G} u = min { y , t j } ∈ G if s < a s<a s < a (since t j ≤ U t_j\le U t j ≤ U ). Direct substitution gives E j ( y ; a ) E_j(y;a) E j ( y ; a ) in both cases. □ \square □
Lemma 3.4 (Exact three-regime comparator threshold). Consider an adjacent pair L = ( f L , v L , π L , t L ) L=(f_L,v_L,\pi_L,t_L) L = ( f L , v L , π L , t L ) and R = ( f R , v R , π R , t R ) R=(f_R,v_R,\pi_R,t_R) R = ( f R , v R , π R , t R ) satisfying f L ≤ t L ≤ f R ≤ t R f_L \le t_L \le f_R \le t_R f L ≤ t L ≤ f R ≤ t R and π L ≥ π R \pi_L \ge\pi_R π L ≥ π R . Put
λ L = t L − f L ≥ 0 , Δ t = t R − t L ≥ 0 , λ R = t R − f R ≥ 0 , δ = f R − f L ≥ 0. \lambda_L=t_L-f_L\ge0,\qquad\Delta_t=t_R-t_L\ge0,\qquad\lambda_R=t_R-f_R\ge0,\qquad\delta=f_R-f_L\ge0. λ L = t L − f L ≥ 0 , Δ t = t R − t L ≥ 0 , λ R = t R − f R ≥ 0 , δ = f R − f L ≥ 0. Note that λ L + Δ t − λ R = δ \lambda_L+\Delta_t-\lambda_R=\delta λ L + Δ t − λ R = δ . Extending the right-checkpoint difference algebraically to all c ∈ R c\in\mathbb{R} c ∈ R by
D ( c ) = E L ( t R ; c ) − E R ( t R ; c ) = v L − v R + λ L min { π L , c } + Δ t c − λ R min { π R , c } , (40) D(c)=E_L(t_R;c)-E_R(t_R;c)=v_L-v_R+\lambda_L\min\{\pi_L,c\}+\Delta_t c-\lambda_R\min\{\pi_R,c\}, \tag*{(40)} D ( c ) = E L ( t R ; c ) − E R ( t R ; c ) = v L − v R + λ L min { π L , c } + Δ t c − λ R min { π R , c } , (40) the function D : R → R D:\mathbb{R}\to\mathbb{R} D : R → R is continuous and nondecreasing, and
θ = sup { c ∈ R : D ( c ) ≤ 0 } ∈ [ − ∞ , + ∞ ] (41) \theta=\sup\{c\in\mathbb{R}:D(c)\le0\}\in[-\infty,+\infty] \tag*{(41)} θ = sup { c ∈ R : D ( c ) ≤ 0 } ∈ [ − ∞ , + ∞ ] (41) is computable in O ( 1 ) O(1) O ( 1 ) time. For every comparator c ≥ 0 c\ge0 c ≥ 0 , candidate L L L dominates candidate R R R on [ f R , + ∞ ) [f_R,+\infty) [ f R , + ∞ ) if and only if c ≤ θ c\le\theta c ≤ θ .
Proof. For finite labels π R ≤ π L \pi_R\le\pi_L π R ≤ π L , (3.6) splits into three affine pieces:
D ( c ) = { v L − v R + δ c , c ≤ π R , v L − v R − λ R π R + ( t R − f L ) c , π R ≤ c ≤ π L , v L − v R + λ L π L − λ R π R + Δ t c , c ≥ π L , (42) D(c)=
\begin{cases}
v_L-v_R+\delta c, & c\le\pi_R,\\
v_L-v_R-\lambda_R\pi_R+(t_R-f_L)c, & \pi_R\le c\le\pi_L,\\
v_L-v_R+\lambda_L\pi_L-\lambda_R\pi_R+\Delta_t c, & c\ge\pi_L,
\end{cases} \tag*{(42)} D ( c ) = ⎩ ⎨ ⎧ v L − v R + δ c , v L − v R − λ R π R + ( t R − f L ) c , v L − v R + λ L π L − λ R π R + Δ t c , c ≤ π R , π R ≤ c ≤ π L , c ≥ π L , (42) whose slopes δ ≥ 0 \delta\ge0 δ ≥ 0 , t R − f L = δ + λ R ≥ 0 t_R-f_L=\delta+\lambda_R\ge0 t R − f L = δ + λ R ≥ 0 , and Δ t ≥ 0 \Delta_t\ge0 Δ t ≥ 0 are all nonnegative, and whose endpoint values match at π R \pi_R π R and π L ( i f \pi_L (if π L ( i f \pi_L=+\infty$ or π R = + ∞ \pi_R=+\infty π R = + ∞ , omit the corresponding upper regime(s)). Thus { c ∈ R : D ( c ) ≤ 0 } \{c\in\mathbb{R}:D(c)\le0\} { c ∈ R : D ( c ) ≤ 0 } is an initial interval ( − ∞ , θ ] (-\infty,\theta] ( − ∞ , θ ] (or ∅ \varnothing ∅ with θ = − ∞ \theta=-\infty θ = − ∞ , or R \mathbb{R} R with θ = + ∞ \theta=+\infty θ = + ∞ ). Solving the affine inequality on each regime handles zero slopes (δ = 0 \delta=0 δ = 0 or Δ t = 0 \Delta_t=0 Δ t = 0 ) directly without division by zero. Equivalence with full-domain domination follows from Lemma 3.2(1).
Retaining finite negative values of θ \theta θ (rather than clamping negative roots to − ∞ -\infty − ∞ ) ensures exact invariance under holding-cost additions: adding h i x h_i x h i x to all curves maps ( v j , π j , c ) ↦ ( v j + h i f j , π j + h i , c + h i ) (v_j,\pi_j,c)\mapsto(v_j+h_i f_j,\pi_j+h_i,c+h_i) ( v j , π j , c ) ↦ ( v j + h i f j , π j + h i , c + h i ) , which satisfies D n e w ( c + h i ) = D o l d ( c ) D_{\mathrm{new}}(c+h_i)=D_{\mathrm{old}}(c) D new ( c + h i ) = D old ( c ) and shifts every finite threshold by θ n e w = θ o l d + h i \theta_{\mathrm{new}}=\theta_{\mathrm{old}}+h_i θ new = θ old + h i , while demand translations x ↦ x − d i x\mapsto x-d_i x ↦ x − d i preserve λ L , Δ t , λ R , δ \lambda_L,\Delta_t,\lambda_R,\delta λ L , Δ t , λ R , δ and leave θ \theta θ unchanged.
Theorem 3.5 (Completeness of adjacent pruning). Starting from any family satisfying (3.2) at comparator c ≥ 0 c\ge0 c ≥ 0 , repeatedly deleting the right candidate of any adjacent pair with θ ≥ c \theta\ge c θ ≥ c (and coalescing coincident pure-linear pairs) preserves the lower envelope C C C , maintains (3.2), restores (3.3) upon termination, and performs exactly one step per deleted candidate.
Proof. By Lemma 3.4, θ ≥ c ⟺ D ( c ) ≤ 0 \theta\ge c\Longleftrightarrow D(c)\le0 θ ≥ c ⟺ D ( c ) ≤ 0 , so E L ( x ; c ) ≤ E R ( x ; c ) E_L(x;c)\le E_R(x;c) E L ( x ; c ) ≤ E R ( x ; c ) for all x ≥ f R x\ge f_R x ≥ f R , making R R R redundant. Deleting R R R preserves (3.2) and affects only the adjacency between L L L and succ ( R ) \operatorname{succ}(R) succ ( R ) . When θ < c \theta<c θ < c holds for all remaining adjacent pairs, D ( c ) > 0 D(c)>0 D ( c ) > 0 holds everywhere, establishing (3.3).
Bulk ray generation, domain clipping, and merge truncation
Lemma 3.6 (Bulk rays from eligible anchors and parallel-record normalization). Suppose C C C is represented on [ 0 , U ] [0,U] [ 0 , U ] at comparator c ≥ β i c\ge\beta_i c ≥ β i with π j ≥ β i \pi_j\ge\beta_i π j ≥ β i for every candidate j j j . Then for all y ∈ [ 0 , Y i ] ∩ G y\in[0,Y_i]\cap\mathcal{G} y ∈ [ 0 , Y i ] ∩ G ,
( D β i , d i C ) ( y ) = min j : f j < d i f j + Q ≤ y { v j + β i ( y − f j ) } . (43) (D_{\beta_i,d_i}C)(y)=\min_{\substack{j:f_j<d_i\\ f_j+Q\le y}}\{v_j+\beta_i(y-f_j)\}. \tag*{(43)} ( D β i , d i C ) ( y ) = j : f j < d i f j + Q ≤ y min { v j + β i ( y − f j )} . (43) For each eligible candidate ( f j < d i (f_j<d_i ( f j < d i and F j = f j + Q ≤ Y i ) F_j=f_j+Q\le Y_i) F j = f j + Q ≤ Y i ) , set V j = v j + Q β i V_j=v_j+Q\beta_i V j = v j + Q β i and intercept η j = V j − β i F j = v j − β i f j \eta_j=V_j-\beta_iF_j=v_j-\beta_i f_j η j = V j − β i F j = v j − β i f j . Retaining the minimum-value ray at equal anchors and keeping only
strict prefix-record minima of η j \eta_j η j in increasing order of F j F_j F j produces surviving records 1 , … , k 1,\ldots,k 1 , … , k whose lower envelope on [ 0 , Y i ] ∩ G [0,Y_i]\cap G [ 0 , Y i ] ∩ G is represented in normal form (at any comparator c ≥ β i c\ge\beta_i c ≥ β i ) by ( F r , V r , β i , T r ) (F_r,V_r,\beta_i,T_r) ( F r , V r , β i , T r ) with
T r = { F r + 1 , 1 ≤ r < k when G = R ≥ 0 , F r + 1 − 1 , 1 ≤ r < k when G = Z ≥ 0 , Y i , r = k , (44) T_r =
\begin{cases}
F_{r+1}, & 1\le r<k\text{ when }G=\mathbb{R}_{\ge0},\\
F_{r+1}-1, & 1\le r<k\text{ when }G=\mathbb{Z}_{\ge0},\\
Y_i, & r=k,
\end{cases} \tag*{(44)} T r = ⎩ ⎨ ⎧ F r + 1 , F r + 1 − 1 , Y i , 1 ≤ r < k when G = R ≥ 0 , 1 ≤ r < k when G = Z ≥ 0 , r = k , (44)
and exact adjacent thresholds equal to the anchor secants
θ r = R r = V r + 1 − V r F r + 1 − F r < β i , r = 1 , … , k − 1. (45) \theta_r=R_r=\frac{V_{r+1}-V_r}{F_{r+1}-F_r}<\beta_i,\qquad r=1,\ldots,k-1. \tag*{(45)} θ r = R r = F r + 1 − F r V r + 1 − V r < β i , r = 1 , … , k − 1. (45)
Proof. On each candidate j j j , min { π j , c } ≥ β i \min\{\pi_j,c\}\ge\beta_i min { π j , c } ≥ β i and c ≥ β i c\ge\beta_i c ≥ β i , so u ↦ E j ( u ; c ) − β i u u\mapsto E_j(u;c)-\beta_i u u ↦ E j ( u ; c ) − β i u is nondecreasing for u ≥ f j u\ge f_j u ≥ f j . Whenever candidate j j j has a feasible source u ∈ [ f j , d i ) u\in[f_j,d_i) u ∈ [ f j , d i ) with u + Q ≤ y u+Q\le y u + Q ≤ y , u = f j u=f_j u = f j is also feasible and attains its minimum, proving (3.9). Because all shifted candidates V j + β i ( y − F j ) = η j + β i y V_j+\beta_i(y-F_j)=\eta_j+\beta_i y V j + β i ( y − F j ) = η j + β i y are parallel rays of slope β i \beta_i β i , a ray is optimal somewhere if and only if its intercept η j \eta_j η j sets a strict new minimum in anchor order; record r r r then wins on [ F r , F r + 1 ) [F_r,F_{r+1}) [ F r , F r + 1 ) (or { F r , … , F r + 1 − 1 } \{F_r,\ldots,F_{r+1}-1\} { F r , … , F r + 1 − 1 } in Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 ), and raising its continuation beyond T r T_r T r to slope c ≥ β i c\ge\beta_i c ≥ β i leaves the combined lower envelope unchanged because record r + 1 r+1 r + 1 is strictly cheaper from F r + 1 F_{r+1} F r + 1 onward.
Finally, for c ≤ β i c\le\beta_i c ≤ β i , substituting π r = π r + 1 = β i \pi_r=\pi_{r+1}=\beta_i π r = π r + 1 = β i into (3.6) gives min { β i , c } = c \min\{\beta_i,c\}=c min { β i , c } = c , so both T r T_r T r and T r + 1 T_{r+1} T r + 1 cancel identically in both R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 and Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 :
D r ( c ) = V r − V r + 1 + ( ( T r − F r ) + ( T r + 1 − T r ) − ( T r + 1 − F r + 1 ) ) c = V r − V r + 1 + ( F r + 1 − F r ) c . D_r(c)=V_r-V_{r+1}+\bigl((T_r-F_r)+(T_{r+1}-T_r)-(T_{r+1}-F_{r+1})\bigr)c
=V_r-V_{r+1}+(F_{r+1}-F_r)c. D r ( c ) = V r − V r + 1 + ( ( T r − F r ) + ( T r + 1 − T r ) − ( T r + 1 − F r + 1 ) ) c = V r − V r + 1 + ( F r + 1 − F r ) c .
At c = β i c=\beta_i c = β i , D r ( β i ) = η r − η r + 1 > 0 D_r(\beta_i)=\eta_r-\eta_{r+1}>0 D r ( β i ) = η r − η r + 1 > 0 . Monotonicity of D r D_r D r implies D r ( c ) > 0 D_r(c)>0 D r ( c ) > 0 for all c ≥ β i c\ge\beta_i c ≥ β i and yields the unique root θ r = R r < β i \theta_r=R_r<\beta_i θ r = R r < β i in (3.11).
Lemma 3.7 (Domain clipping and merge-boundary truncation). Let a normal-form family represent C C C on [ 0 , U ] [0,U] [ 0 , U ] at comparator c c c .
Lower-bound clipping to [ ℓ , U ] [\ell,U] [ ℓ , U ] (0 ≤ ℓ ≤ U 0\le\ell\le U 0 ≤ ℓ ≤ U ): Let j j j be the last candidate with t j ≤ ℓ t_j\le\ell t j ≤ ℓ (if one exists). Discarding indices below j j j , replacing j j j by the pure-linear boundary candidate ( ℓ , E j ( ℓ ; c ) , π j , ℓ ) (\ell,E_j(\ell;c),\pi_j,\ell) ( ℓ , E j ( ℓ ; c ) , π j , ℓ ) , and—if j + 1 j+1 j + 1 (or 1 1 1 , when j j j does not exist) has f < ℓ < t f<\ell<t f < ℓ < t —reanchoring that single curve at ( ℓ , E ( ℓ ; c ) , π , t ) (\ell,E(\ell;c),\pi,t) ( ℓ , E ( ℓ ; c ) , π , t ) reproduces C C C on [ ℓ , U ] [\ell,U] [ ℓ , U ] while creating at most two boundary records and preserving slope-label monotonicity (3.2) (coalescing if f j + 1 = t j + 1 = ℓ f_{j+1}=t_{j+1}=\ell f j + 1 = t j + 1 = ℓ ). At any resulting equal-anchor pair ( ℓ , v , π j , ℓ ) (\ell,v,\pi_j,\ell) ( ℓ , v , π j , ℓ ) and ( ℓ , w , π , t ) (\ell,w,\pi,t) ( ℓ , w , π , t ) with t > ℓ t>\ell t > ℓ , the pure-linear curve is dropped if w ≤ v w\le v w ≤ v , the legacy curve is dropped if ( v − w ) + ( c − min { π , c } ) ( t − ℓ ) ≤ 0 (v-w)+(c-\min\{\pi,c\})(t-\ell)\le0 ( v − w ) + ( c − min { π , c }) ( t − ℓ ) ≤ 0 , and otherwise both are retained in normal form.
Upper-bound and strict-prefix clipping: For [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] (0 ≤ ℓ ≤ U 0\le\ell\le U 0 ≤ ℓ ≤ U ), discarding candidates with f j > ℓ f_j>\ell f j > ℓ , shortening at most the last remaining endpoint t j > ℓ t_j>\ell t j > ℓ to ℓ \ell ℓ , and deleting (or coalescing) that single boundary candidate if it violates (3.3) at ℓ \ell ℓ preserves C C C on [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] in normal form. For a strict prefix u < d i u<d_i u < d i , return ∅ \varnothing ∅ if d i = 0 d_i=0 d i = 0 ; clip to [ 0 , d i − 1 ] [0,d_i-1] [ 0 , d i − 1 ] if G = Z ≥ 0 G=\mathbb{Z}_{\ge0} G = Z ≥ 0 and d i ≥ 1 d_i\ge1 d i ≥ 1 ; and if G = R ≥ 0 G=\mathbb{R}_{\ge0} G = R ≥ 0 and d i > 0 d_i>0 d i > 0 , discard candidates with f j ≥ d i f_j\ge d_i f j ≥ d i , shorten any remaining t j > d i t_j>d_i t j > d i to d i d_i d i , and delete that shortened boundary candidate if it violates (3.3) at d i d_i d i .
Merge truncation at ξ ∈ [ d i , Y i ] ∩ G \xi\in[d_i,Y_i]\cap G ξ ∈ [ d i , Y i ] ∩ G : Suppose normal-form families R R R (representing O i O_i O i on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] at comparator α i \alpha_i α i , with π j ≥ β i \pi_j\ge\beta_i π j ≥ β i ) and X X X (representing N i N_i N i on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] at comparator α i \alpha_i α i , with π j = β i \pi_j=\beta_i π j = β i ) satisfy N i ( x ) ≤ O i ( x ) N_i(x)\le O_i(x) N i ( x ) ≤ O i ( x ) for all x ∈ [ ξ , Y i ] ∩ G x\in[\xi,Y_i]\cap G x ∈ [ ξ , Y i ] ∩ G . If ξ = d i \xi=d_i ξ = d i , then min { O i , N i } = N i \min\{O_i,N_i\}=N_i min { O i , N i } = N i is represented directly by X X X . If ξ > d i \xi>d_i ξ > d i , clipping R R R to the strict prefix u < ξ u<\xi u < ξ via Claim 2, lower-clipping X X X to [ ξ , Y i ] [\xi,Y_i] [ ξ , Y i ] via Claim 1, joining the two fragments, and deleting the first node of the right fragment if the seam threshold satisfies θ ≥ α i \theta\ge\alpha_i θ ≥ α i produces min { O i , N i } \min\{O_i,N_i\} min { O i , N i } on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] in normal form.
Proof. In Claim 1, Lemma 3.2 (2) shows that candidate j j j dominates all h < j h<j h < j on [ ℓ , U ] [\ell,U] [ ℓ , U ] and equals a pure regular line of slope c c c there; keeping its label π j \pi_j π j leaves E j ( x ; c ) = E j ( ℓ ; c ) + c ( x − ℓ ) E_j(x;c)=E_j(\ell;c)+c(x-\ell) E j ( x ; c ) = E j ( ℓ ; c ) + c ( x − ℓ ) unchanged because t − f = 0 t-f=0 t − f = 0 , while preserving π 1 ≥ ⋯ ≥ π m \pi_1\ge\cdots\ge\pi_m π 1 ≥ ⋯ ≥ π m . Interleaving ensures at most one successor has f < ℓ < t f<\ell<t f < ℓ < t , and the equal-anchor rule compares the two affine branches at ℓ \ell ℓ and t t t , between which their difference is monotone and beyond which it is constant.
In Claim 2, shortening the last surviving endpoint to ℓ \ell ℓ (or d i d_i d i ) leaves values on [ 0 , ℓ ] [0,\ell] [ 0 , ℓ ] (resp. [ 0 , d i ) [0,d_i) [ 0 , d i ) ) unchanged; if that shortened candidate k k k satisfies E k − 1 ( ℓ ; c ) ≤ E k ( ℓ ; c ) E_{k-1}(\ell;c)\le E_k(\ell;c) E k − 1 ( ℓ ; c ) ≤ E k ( ℓ ; c ) (resp. at d i d_i d i ), Lemma 3.2 (1) implies E k − 1 ( x ; c ) ≤ E k ( x ; c ) E_{k-1}(x;c)\le E_k(x;c) E k − 1 ( x ; c ) ≤ E k ( x ; c ) across [ f k , ℓ ] [f_k,\ell] [ f k , ℓ ] (resp. [ f k , d i ] [f_k,d_i] [ f k , d i ] ), so deleting k k k preserves the prefix envelope and leaves the unshortened predecessor k − 1 k-1 k − 1 satisfying (37) .
In Claim 3, when ξ > d i \xi>d_i ξ > d i , strict-prefix clipping of R R R retains O i O_i O i on [ d i , ξ ) ∩ G [d_i,\xi)\cap G [ d i , ξ ) ∩ G and only raises curves of R R R on [ ξ , Y i ] [\xi,Y_i] [ ξ , Y i ] , where N i ( x ) ≤ O i ( x ) N_i(x)\le O_i(x) N i ( x ) ≤ O i ( x ) already holds. Every retained candidate u ∈ R u\in R u ∈ R has t u ≤ ξ t_u\le\xi t u ≤ ξ (with f u < ξ f_u<\xi f u < ξ , and t u ≤ ξ − 1 t_u\le\xi-1 t u ≤ ξ − 1 on Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 ) and π u ≥ β i \pi_u\ge\beta_i π u ≥ β i , whereas the first candidate w w w of clipped X X X has anchor f w = ξ f_w=\xi f w = ξ and π w = β i \pi_w=\beta_i π w = β i , so (36) and strict key ordering ( t u , f u ) < ( t w , f w ) (t_u,f_u)<(t_w,f_w) ( t u , f u ) < ( t w , f w ) hold across the seam. If θ u ≥ α i \theta_u\ge\alpha_i θ u ≥ α i deletes w w w , any successor w ′ = succ ( w ) w'=\operatorname{succ}(w) w ′ = succ ( w ) in X X X has anchor F r + 1 > ξ F_{r+1}>\xi F r + 1 > ξ with strict intercept drop V r + 1 < V r + β i ( F r + 1 − F r ) ≤ E u ( F r + 1 ; α i ) V_{r+1}<V_r+\beta_i(F_{r+1}-F_r)\le E_u(F_{r+1};\alpha_i) V r + 1 < V r + β i ( F r + 1 − F r ) ≤ E u ( F r + 1 ; α i ) and slope β i ≤ α i \beta_i\le\alpha_i β i ≤ α i up to T w ′ T_{w'} T w ′ , forcing E u ( T w ′ ; α i ) > E w ′ ( T w ′ ; α i ) E_u(T_{w'};\alpha_i)>E_{w'}(T_{w'};\alpha_i) E u ( T w ′ ; α i ) > E w ′ ( T w ′ ; α i ) and hence θ u < α i \theta_u<\alpha_i θ u < α i immediately.
Balanced-Tree Implementation and Amortized Complexity
We implement the auxiliary recurrence (2.27)–(2.30) using an augmented height-balanced binary search tree T T T supporting worst-case O ( log m ) O(\log m) O ( log m ) -time search, insertion, deletion, split, and join on m m m nodes [3 , 4 ] .
Node augmentation and lazy-tag algebra
Nodes are ordered by ( t j , f j ) (t_j,f_j) ( t j , f j ) . Each node stores ( f j , v j , π j , t j ) (f_j,v_j,\pi_j,t_j) ( f j , v j , π j , t j ) , a cached successor anchor succAnchor j \operatorname{succAnchor}_j succAnchor j , the exact threshold θ j \theta_j θ j of Lemma 3.4 and anchor secant R j = ( v j + 1 − v j ) / ( f j + 1 − f j ) R_j=(v_{j+1}-v_j)/(f_{j+1}-f_j) R j = ( v j + 1 − v j ) / ( f j + 1 − f j ) (with R j = + ∞ R_j=+\infty R j = + ∞ when f j = f j + 1 f_j=f_{j+1} f j = f j + 1 , and θ m = R m = − ∞ \theta_m=R_m=-\infty θ m = R m = − ∞ at the rightmost node of a fragment), scalar subtree maxima maxTheta \operatorname{maxTheta} maxTheta and maxR \operatorname{maxR} maxR , subtree first/last anchors and endpoints, and constant-size lazy tags:
an affine coordinate/value tag T ( δ x , δ s , δ v ) \mathcal{T}(\delta_x,\delta_s,\delta_v) T ( δ x , δ s , δ v ) acting as ( x , v ) ↦ ( x + δ x , v + δ s x + δ v ) (x,v)\mapsto(x+\delta_x,v+\delta_sx+\delta_v) ( x , v ) ↦ ( x + δ x , v + δ s x + δ v ) , composed via
T ( δ x , 2 , δ s , 2 , δ v , 2 ) ∘ T ( δ x , 1 , δ s , 1 , δ v , 1 ) = T ( δ x , 1 + δ x , 2 , δ s , 1 + δ s , 2 , δ v , 1 + δ v , 2 + δ s , 2 δ x , 1 ) ; (46) \mathcal{T}(\delta_{x,2},\delta_{s,2},\delta_{v,2})\circ\mathcal{T}(\delta_{x,1},\delta_{s,1},\delta_{v,1})
=\mathcal{T}(\delta_{x,1}+\delta_{x,2},\delta_{s,1}+\delta_{s,2},\delta_{v,1}+\delta_{v,2}+\delta_{s,2}\delta_{x,1}); \tag*{(46)} T ( δ x , 2 , δ s , 2 , δ v , 2 ) ∘ T ( δ x , 1 , δ s , 1 , δ v , 1 ) = T ( δ x , 1 + δ x , 2 , δ s , 1 + δ s , 2 , δ v , 1 + δ v , 2 + δ s , 2 δ x , 1 ) ; (46)
a legacy-slope tag storing an optional bulk assignment π ← β \pi\leftarrow\beta π ← β plus an accumulated holding shift + Δ h +\Delta_h + Δ h on finite labels;
a per-node endpoint-mode bit (‘fixed’ vs. ‘succSnapshot’, where ‘succSnapshot’ evaluates t j = succAnchor j t_j=\operatorname{succAnchor}_j t j = succAnchor j in R ≥ 0 \mathbb{R}_{\ge0} R ≥ 0 and succAnchor j − 1 \operatorname{succAnchor}_j-1 succAnchor j − 1 in Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 ) paired with a lazy subtree flag ‘setSuccSnapshot’ that switches all nodes in a subtree to ‘succSnapshot’ mode as tags are pushed down;
a threshold-key tag supporting uniform holding shifts ( θ , R ) ↦ ( θ + Δ h , R + Δ h ) (\theta,R)\mapsto(\theta+\Delta_h,R+\Delta_h) ( θ , R ) ↦ ( θ + Δ h , R + Δ h ) and lazy bulk copy ( θ , R ) ↦ ( R , R ) (\theta,R)\mapsto(R,R) ( θ , R ) ↦ ( R , R ) , which commute: H Δ h ∘ B = B ∘ H Δ h H_{\Delta_h}\circ B=B\circ H_{\Delta_h} H Δ h ∘ B = B ∘ H Δ h .
Queries ArgMaxTheta ( T ) \operatorname{ArgMaxTheta}(T) ArgMaxTheta ( T ) and ArgMaxR ( T ) \operatorname{ArgMaxR}(T) ArgMaxR ( T ) , together with inorder neighbor lookups pred ( j ) \operatorname{pred}(j) pred ( j ) and succ ( j ) \operatorname{succ}(j) succ ( j ) , descend from the root in O ( log m ) O(\log m) O ( log m ) time using child subtree aggregates while pushing pending lazy tags along the visited root-to-node paths.
Crucially, ‘succSnapshot’ represents the successor anchor at the moment of bulk normalization, not a live pointer to future successors. Before any structural edit mutates an inorder adjacency, the affected root-to-node search paths are exposed (pushing pending lazy tags) and the owner’s ‘succSnapshot’ endpoint is materialized into ‘fixed’ mode before its cached succAnchor is updated. Consequently, deleting a neighbor never retroactively extends an already-truncated legacy branch, and every split, join, or constant-size crop repairs O ( 1 ) O(1) O ( 1 ) adjacencies in O ( log m ) O(\log m) O ( log m ) time.
Regular closure, bulk rays, and bracket-guarded merge
Algorithms 1 and 2 implement Lemmas 3.3–3.6. Every nonterminating iteration of either loop deletes a node permanently in O ( log m ) O(\log m) O ( log m ) time, and the final bulk normalization in Algorithm 2 takes O ( log m ) O(\log m) O ( log m ) time with zero linear scan.
After splitting O i O_i O i into X X X (u < d i u < d_i u < d i ) and R R R (u ≥ d i u \ge d_i u ≥ d i ), constructing X ← DiscountedRays ( X , Q , β i , Y i ) X \leftarrow\operatorname{DiscountedRays}(X,Q,\beta_i,Y_i) X ← DiscountedRays ( X , Q , β i , Y i ) , and lower-clipping X X X to [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] , we merge R R R and X X X across the overlap [ L i , Y i ] [L_i,Y_i] [ L i , Y i ] , where L i = max { Q , d i } ≤ Y i = d i + 2 Q L_i = \max\{Q,d_i\} \le Y_i = d_i + 2Q L i = max { Q , d i } ≤ Y i = d i + 2 Q . Algorithm 3 gives the backward-sweep merge, and Lemma 4.1 establishes the O ( log m ) O(\log m) O ( log m ) bracket-guarded crossover search.
Lemma 4.1 (Bracket-guarded crossover search and merge complexity). In Algorithm 3, whenever FirstTakeover is invoked on [ s , e ] [s,e] [ s , e ] , we have L i ≤ s < e ≤ Y i L_i \le s < e \le Y_i L i ≤ s < e ≤ Y i , Value ( X , s ) > O i ( s ) \operatorname{Value}(X,s) > O_i(s) Value ( X , s ) > O i ( s ) , Value ( X , e ) ≤ O i ( e ) \operatorname{Value}(X,e) \le O_i(e) Value ( X , e ) ≤ O i ( e ) , and O i ( x ) O_i(x) O i ( x ) on [ s , e ) [s,e) [ s , e ) equals the minimum of at most two exposed candidate equations ( E l e f t , E r i g h t ) (E_{\mathrm{left}},E_{\mathrm{right}}) ( E left , E right ) of R R R . Guarding the binary search on X X X so that anchors F w ≤ s F_w \le s F w ≤ s record a ← w a \leftarrow w a ← w and branch right without evaluating (4.2), anchors F w ≥ e F_w \ge e F w ≥ e branch left without evaluating (4.2), and the predicate
V w ≤ min { E l e f t ( F w ; α i ) , E r i g h t ( F w ; α i ) } (47) V_w \le\min\{E_{\mathrm{left}}(F_w;\alpha_i), E_{\mathrm{right}}(F_w;\alpha_i)\} \tag*{(47)} V w ≤ min { E left ( F w ; α i ) , E right ( F w ; α i )} (47) is evaluated only for anchors F w ∈ ( s , e ) F_w \in(s,e) F w ∈ ( s , e ) (recording a ← w a \leftarrow w a ← w and branching right on failure, or recording b ← w b \leftarrow w b ← w and branching left on success) locates the exact takeover coordinate z ∈ ( s , e ] z \in(s,e] z ∈ ( s , e ] in O ( log m ) O(\log m) O ( log m ) time without nested tree searches. Consequently, a merge deleting k k k nodes from R R R runs in O ( ( k + 1 ) log m ) O((k+1)\log m) O (( k + 1 ) log m ) time, creates O ( 1 ) O(1) O ( 1 ) boundary nodes, and outputs the normal form of F i F_i F i on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] .
Proof. Each deleted node u u u satisfies f u ≥ s f_u \ge s f u ≥ s and N i ( s ) ≤ O i ( s ) N_i(s) \le O_i(s) N i ( s ) ≤ O i ( s ) , so removing u u u leaves Value ( R , x ) = O i ( x ) \operatorname{Value}(R,x) = O_i(x) Value ( R , x ) = O i ( x ) unchanged for all x < s x < s x < s and cannot lower Value ( R , s ) \operatorname{Value}(R,s) Value ( R , s ) at e ← s e \leftarrow s e ← s , preserving Value ( X , e ) ≤ Value ( R , e ) \operatorname{Value}(X,e) \le\operatorname{Value}(R,e) Value ( X , e ) ≤ Value ( R , e ) . Thus entering the ‘else’ branch forces s < e s < e s < e , with no interior endpoint of R R R inside ( s , e ) (s,e) ( s , e ) , so Lemma 3.2(3) expresses O i ( x ) O_i(x) O i ( x ) on [ s , e ) [s,e) [ s , e ) via at most two exposed equations ( E l e f t , E r i g h t ) (E_{\mathrm{left}},E_{\mathrm{right}}) ( E left , E right ) of R R R .
Restricting (4.2) to F w ∈ ( s , e ) F_w \in(s,e) F w ∈ ( s , e ) guarantees that min { E l e f t ( F w ; α i ) , E r i g h t ( F w ; α i ) } = O i ( F w ) \min\{E_{\mathrm{left}}(F_w;\alpha_i),E_{\mathrm{right}}(F_w;\alpha_i)\} = O_i(F_w) min { E left ( F w ; α i ) , E right ( F w ; α i )} = O i ( F w ) is never evaluated outside the valid domain of the exposed pair (avoiding spurious + ∞ +\infty + ∞ values
Algorithm 2: DiscountedRays(X , Q , β i , Y i X, Q, \beta_i, Y_i X , Q , β i , Y i ) — Bulk ray generation and lazy normalization.
Input: Prefix tree X X X representing O i O_i O i on u < d i u < d_i u < d i , threshold Q Q Q , price β i \beta_i β i , departure bound Y i Y_i Y i . Output: Normalized parallel-ray tree X X X representing N i N_i N i on [ 0 , Y i ] [0, Y_i] [ 0 , Y i ] .
If X = ∅ X = \varnothing X = ∅ , return ∅ \varnothing ∅ .
Apply the lazy shift T ( Q , 0 , Q β i ) T(Q, 0, Q\beta_i) T ( Q , 0 , Q β i ) to X X X , mapping ( f j , v j ) ↦ ( f j + Q , v j + Q β i ) (f_j, v_j) \mapsto(f_j + Q, v_j + Q\beta_i) ( f j , v j ) ↦ ( f j + Q , v j + Q β i ) , and discard the suffix of X X X with f j > Y i f_j > Y_i f j > Y i .
while X ≠ ∅ X \ne\varnothing X = ∅ and X . m a x R ≥ β i X.\mathrm{maxR} \ge\beta_i X . maxR ≥ β i do
Locate j ← A r g M a x R ( X ) j \leftarrow\mathrm{ArgMaxR}(X) j ← ArgMaxR ( X ) and k ← s u c c ( j ) k \leftarrow\mathrm{succ}(j) k ← succ ( j ) by top-down search, exposing paths and freezing affected ‘succSnapshot‘ endpoints.
If f j = f k f_j = f_k f j = f k , delete whichever of j , k j, k j , k has the larger anchor value v v v (breaking ties canonically); otherwise delete k k k .
Repair succAnchor and R R R on the updated adjacency, rebalance, and recompute subtree aggregates.
end while
if X ≠ ∅ X \ne\varnothing X = ∅ then
Apply the root lazy tags setting π j ← β i \pi_j \leftarrow\beta_i π j ← β i and ‘setSuccSnapshot‘ across X X X .
Expose the rightmost spine of X X X (pushing ‘setSuccSnapshot‘ along it) and set the rightmost node’s mode to ‘fixed‘ with endpoint Y i Y_i Y i .
Lazily copy active thresholds from secants: ( θ , m a x T h e t a ) ← ( R , m a x R ) (\theta, \mathrm{maxTheta}) \leftarrow(R, \mathrm{maxR}) ( θ , maxTheta ) ← ( R , maxR ) .
end if
return X X X .
Algorithm 3: MergeFrontiers(R R R , X X X , L i L_i L i , Y i Y_i Y i ) — Single-crossing frontier merge.
Input: Old tree R R R on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] , new bulk tree X X X on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] , overlap [ L i , Y i ] [L_i,Y_i] [ L i , Y i ] with L i = max { Q , d i } L_i=\max\{Q,d_i\} L i = max { Q , d i } .
Output: Normal-form tree representing F i = min { O i , N i } F_i=\min\{O_i,N_i\} F i = min { O i , N i } on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] .
If X = ∅ X=\varnothing X = ∅ or L i > Y i L_i>Y_i L i > Y i , return R R R .
If Value ( X , Y i ) > Value ( R , Y i ) \operatorname{Value}(X,Y_i)>\operatorname{Value}(R,Y_i) Value ( X , Y i ) > Value ( R , Y i ) , discard X X X and return R R R .
Set right bracket e ← Y i e\leftarrow Y_i e ← Y i .
while R ≠ ∅ R\ne\varnothing R = ∅ do
Let u ← Last ( R ) u\leftarrow\operatorname{Last}(R) u ← Last ( R ) and v ← pred ( u ) v\leftarrow\operatorname{pred}(u) v ← pred ( u ) ; set s ← max { L i , t v } s\leftarrow\max\{L_i,t_v\} s ← max { L i , t v } if v v v exists, else s ← L i s\leftarrow L_i s ← L i .
if Value ( X , s ) ≤ Value ( R , s ) \operatorname{Value}(X,s)\le\operatorname{Value}(R,s) Value ( X , s ) ≤ Value ( R , s ) then
If f u < s f_u<s f u < s (which forces s = L i s=L_i s = L i ), set z ← L i z\leftarrow L_i z ← L i and break .
Freeze affected snapshots, delete u u u from R R R , repair neighbors, and set e ← s e\leftarrow s e ← s .
else
Expose the at-most-two candidate equations of R R R governing [ s , e ) [s,e) [ s , e ) .
Set z ← FirstTakeover ( X , [ s , e ] , exposed old equations ) z\leftarrow\operatorname{FirstTakeover}(X,[s,e],\text{ exposed old equations}) z ← FirstTakeover ( X , [ s , e ] , exposed old equations ) and break .
end if
end while
If R = ∅ R=\varnothing R = ∅ , set z ← L i z\leftarrow L_i z ← L i .
Apply merge truncation at ξ = z \xi=z ξ = z via Lemma 3.7 (3) (returning X X X if z = d i z=d_i z = d i ; otherwise clipping R R R to u < z u<z u < z , lower-clipping X X X to [ z , Y i ] [z,Y_i] [ z , Y i ] , joining the fragments, and pruning at most one seam node if θ ≥ α i \theta\ge\alpha_i θ ≥ α i ), and return the resulting tree.
at anchors of X X X below f l e f t ≤ s f_{\mathrm{left}}\le s f left ≤ s ), while recording a ← w a\leftarrow w a ← w whenever F w ≤ s F_w\le s F w ≤ s is valid because Value ( X , s ) > O i ( s ) \operatorname{Value}(X,s)>O_i(s) Value ( X , s ) > O i ( s ) rules out takeover at or before s s s . By Theorem 2.11 , (47) is monotone across F w ∈ ( s , e ) F_w\in(s,e) F w ∈ ( s , e ) . Initializing a ← n i l a\leftarrow\mathrm{nil} a ← nil and sentinel F b ← e F_b\leftarrow e F b ← e , the O ( log m ) O(\log m) O ( log m ) search finds the last anchor F a < e F_a<e F a < e not yet winning at its anchor (if any exists) and the first anchor F b > s F_b>s F b > s winning at its anchor (or sentinel e e e ). On ( max { s , F a } , min { e , F b } ) (\max\{s,F_a\},\min\{e,F_b\}) ( max { s , F a } , min { e , F b }) (taking max { s , F a } = s \max\{s,F_a\}=s max { s , F a } = s when a = n i l a=\mathrm{nil} a = nil ), either a = n i l a=\mathrm{nil} a = nil (N i = + ∞ N_i=+\infty N i = + ∞ there, so takeover occurs at the jump z = F b z=F_b z = F b ), or N i ( x ) = V a + β i ( x − F a ) N_i(x)=V_a+\beta_i(x-F_a) N i ( x ) = V a + β i ( x − F a ) is a single line of slope β i \beta_i β i compared against the constant-size piecewise-affine curve min { E l e f t , E r i g h t } \min\{E_{\mathrm{left}},E_{\mathrm{right}}\} min { E left , E right } (solving O ( 1 ) O(1) O ( 1 ) affine inequalities, or rounding up in Z ≥ 0 \mathbb{Z}_{\ge0} Z ≥ 0 , and defaulting to z = F b z=F_b z = F b if no crossing precedes F b F_b F b ). Truncation and seam repair follow Lemma 3.7 (3).
Online per-period algorithm and proof of Theorem 1.1
Proof of Theorem 1.1 . We first verify correctness by induction on i i i . At i = 1 i=1 i = 1 , T T T represents A 1 ( 0 ) = 0 A_1(0)=0 A 1 ( 0 ) = 0 on [ 0 , 0 ] [0,0] [ 0 , 0 ] . Suppose T T T represents A i A_i A i in normal form on [ 0 , K i ] [0,K_i] [ 0 , K i ] at entry to period i i i , with stored comparator α i − 1 + h i − 1 \alpha_{i-1}+h_{i-1} α i − 1 + h i − 1 (for i ≥ 2 i\ge2 i ≥ 2 ) and all finite legacy labels satisfying π j ≥ β i − 1 + h i − 1 \pi_j\ge\beta_{i-1}+h_{i-1} π j ≥ β i − 1 + h i − 1 . By (9) , α i ≤ α i − 1 + h i − 1 \alpha_i\le\alpha_{i-1}+h_{i-1} α i ≤ α i − 1 + h i − 1 and β i ≤ β i − 1 + h i − 1 ≤ π j \beta_i\le\beta_{i-1}+h_{i-1}\le\pi_j β i ≤ β i − 1 + h i − 1 ≤ π j , so Lemma 3.3 and Algorithm 1 produce O i O_i O i on [ 0 , Y i ] [0,Y_i] [ 0 , Y i ] (note K i = 2 Q ≤ d i + 2 Q = Y i K_i=2Q\le d_i+2Q=Y_i K i = 2 Q ≤ d i + 2 Q = Y i , so no incoming upper crop is even needed). By Lemma 2.8 (D β i , d i O α i A i = D β i , d i A i D_{\beta_i,d_i}O_{\alpha_i}A_i=D_{\beta_i,d_i}A_i D β i , d i O α i A i = D β i , d i A i ) and Lemma 3.6 , Step 7 produces N i N_i N i restricted to [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] . By Lemma 4.1 , Step 8 produces F i = min { O i , N i } F_i=\min\{O_i,N_i\} F i = min { O i , N i } on [ d i , Y i ] [d_i,Y_i] [ d i , Y i ] , so Step 9 records Z i = F i ( d i ) = A i + 1 ( 0 ) = OPT i , 0 Z_i=F_i(d_i)=A_{i+1}(0)=\operatorname{OPT}_{i,0} Z i = F i ( d i ) = A i + 1 ( 0 ) = OPT i , 0 by Theorem 2.7 . Step 10 maps departure coordinate y = d i + z ∈ [ d i , d i + 2 Q ] y=d_i+z\in[d_i,d_i+2Q] y = d i + z ∈ [ d i , d i + 2 Q ] to arrival coordinate z ∈ [ 0 , 2 Q ] z\in[0,2Q] z ∈ [ 0 , 2 Q ] and adds h i ( y − d i ) = h i z h_i(y-d_i)=h_i z h i ( y − d i ) = h i z , yielding A i + 1 ( z ) = F i ( d i + z ) + h i z A_{i+1}(z)=F_i(d_i+z)+h_i z A i + 1 ( z ) = F i ( d i + z ) + h i z with comparator α i + h i \alpha_i+h_i α i + h i and finite labels ≥ β i + h i \ge\beta_i+h_i ≥ β i + h i . After period n n n , every candidate slope in A n + 1 A_{n+1} A n + 1 is at least β n + h n ≥ 0 \beta_n+h_n\ge0 β n + h n ≥ 0 , so each candidate attains its minimum at its anchor f j ∈ [ 0 , 2 Q ] f_j\in[0,2Q] f j ∈ [ 0 , 2 Q ] , giving min 0 ≤ z ≤ 2 Q A n + 1 ( z ) = min j E j 0 = OPT \min_{0\le z\le2Q}A_{n+1}(z)=\min_j E_j^0=\operatorname{OPT} min 0 ≤ z ≤ 2 Q A n + 1 ( z ) = min j E j 0 = OPT by Theorem 2.7 .
For time and space complexity, T T T starts with 1 node, and each period i i i performs O ( 1 ) O(1) O ( 1 ) splits, clips, and joins that create at most a constant number of boundary nodes; bulk updates mutate existing nodes lazily without copying. Hence at most O ( n ) O(n) O ( n ) candidate nodes are ever created, bounding ∣ T ∣ = O ( n ) |T| = O(n) ∣ T ∣ = O ( n ) at all times and total deletions across all invocations of Algorithms 1–3 by O ( n ) O(n) O ( n ) . Charging each nonterminal while-loop iteration to its permanent node deletion at O ( log n ) O(\log n) O ( log n ) per deletion, and adding O ( log n ) O(\log n) O ( log n ) per period for constant-count splits, point queries, and the guarded crossover search, yields O ( n log n ) O(n \log n) O ( n log n ) total time. Each node stores O ( 1 ) O(1) O ( 1 ) fields and no historical tree versions are retained, so working space is O ( n ) O(n) O ( n ) (and strictly O ( n ) O(n) O ( n ) even if only OPT is streamed, with O ( 1 ) O(1) O ( 1 ) scalar state outside T T T ). Note that Steps 2–9 require no knowledge of n n n or future periods.
Algorithm 4: Online O ( n log n ) O(n \log n) O ( n log n ) Optimal-Value Algorithm for Arbitrary Uncapacitated Prices.
Input: Horizon n n n , threshold Q > 0 Q > 0 Q > 0 , sequential stream ( d i , p 1 , i , p 2 , i , h i ) (d_i, p_{1,i}, p_{2,i}, h_i) ( d i , p 1 , i , p 2 , i , h i ) for i = 1 , … , n i = 1, \ldots, n i = 1 , … , n .
Output: Free-terminal optimum OPT and zero-terminal prefix optima ( Z 1 , … , Z n ) (Z_1, \ldots, Z_n) ( Z 1 , … , Z n ) .
Initialize T T T with the single candidate ( f 1 = 0 , v 1 = 0 , π 1 = + ∞ , t 1 = 0 ) (f_1 = 0, v_1 = 0, \pi_1 = +\infty, t_1 = 0) ( f 1 = 0 , v 1 = 0 , π 1 = + ∞ , t 1 = 0 ) on [ 0 , 0 ] [0, 0] [ 0 , 0 ] ; set K ← 0 K \leftarrow0 K ← 0 .
for i = 1 , … , n i = 1, \ldots, n i = 1 , … , n do
If i = 1 i = 1 i = 1 , set α 1 ← p 1 , 1 \alpha_1 \leftarrow p_{1,1} α 1 ← p 1 , 1 , β 1 ← p 2 , 1 \beta_1 \leftarrow p_{2,1} β 1 ← p 2 , 1 ; else set α i ← min { α i − 1 + h i − 1 , p 1 , i } \alpha_i \leftarrow\min\{\alpha_{i-1} + h_{i-1}, p_{1,i}\} α i ← min { α i − 1 + h i − 1 , p 1 , i } and β i ← min { β i − 1 + h i − 1 , p 2 , i } \beta_i \leftarrow\min\{\beta_{i-1} + h_{i-1}, p_{2,i}\} β i ← min { β i − 1 + h i − 1 , p 2 , i } .
Set Y i ← d i + 2 Q Y_i \leftarrow d_i + 2Q Y i ← d i + 2 Q ; extend the target domain of T T T to [ 0 , Y i ] [0, Y_i] [ 0 , Y i ] at comparator α i \alpha_i α i (if i = 1 i = 1 i = 1 , stored comparator starts at α 1 \alpha_1 α 1 ).
T ← RegularClosure ( T , α i ) T \leftarrow\operatorname{RegularClosure}(T, \alpha_i) T ← RegularClosure ( T , α i ) .
( X , R ) ← SplitFrontier ( T , u < d i , u ≥ d i ) (X, R) \leftarrow\operatorname{SplitFrontier}(T, u < d_i,\, u \ge d_i) ( X , R ) ← SplitFrontier ( T , u < d i , u ≥ d i ) via Lemma 3.7 (1)–(2).
X ← DiscountedRays ( X , Q , β i , Y i ) X \leftarrow\operatorname{DiscountedRays}(X, Q, \beta_i, Y_i) X ← DiscountedRays ( X , Q , β i , Y i ) ; lower-clip X X X to targets y ≥ d i y \ge d_i y ≥ d i .
T ← MergeFrontiers ( R , X , max { Q , d i } , Y i ) T \leftarrow\operatorname{MergeFrontiers}(R, X, \max\{Q, d_i\}, Y_i) T ← MergeFrontiers ( R , X , max { Q , d i } , Y i ) ; normalize T T T on [ d i , Y i ] [d_i, Y_i] [ d i , Y i ] .
Record zero-terminal prefix optimum Z i ← Value ( T , d i ) Z_i \leftarrow\operatorname{Value}(T, d_i) Z i ← Value ( T , d i ) .
Apply lazy travel/holding tag T ( − d i , h i , − h i d i ) \mathcal{T}(-d_i, h_i, -h_i d_i) T ( − d i , h i , − h i d i ) , increment finite labels π j \pi_j π j , comparator α i \alpha_i α i , and thresholds ( θ j , R j ) (\theta_j, R_j) ( θ j , R j ) by + h i +h_i + h i , and set arrival domain K ← 2 Q K \leftarrow2Q K ← 2 Q .
end for
Push all remaining lazy tags in a single O ( n ) O(n) O ( n ) traversal of T T T and compute O P T ← min j ∈ T v j \mathrm{OPT} \leftarrow\min_{j \in T} v_j OPT ← min j ∈ T v j .
return OPT and ( Z 1 , … , Z n ) (Z_1, \ldots, Z_n) ( Z 1 , … , Z n ) .
Two-Stage Recovery of an Optimal Physical Schedule
Because an auxiliary candidate’s stored anchor cost v j v_j v j need not equal the lower envelope at f j f_j f j , schedule reconstruction cannot simply store arbitrary parent pointers per node; furthermore, virtual orders in ( α i , β i ) (\alpha_i, \beta_i) ( α i , β i ) must be mapped back to physical purchasing periods. We solve this in two clean stages.
Persistent frontier snapshots and virtual predecessor formulas
Implement T T T via standard path-copying persistence over immutable child links, scalar subtree extrema (maxTheta, maxR, and anchor/endpoint bounds), and cached scalar succAnchor fields [3 , 4 ] . Because ArgMaxTheta, ArgMaxR, neighbor lookups, splits, and joins all operate top-down from the current root using child aggregates, each search-path edit copies O ( log n ) O(\log n) O ( log n ) nodes, pushes lazy tags onto the copied path nodes, and shares unmodified subtrees without parent or mutable thread pointers. Alongside the O ( n ) O(n) O ( n ) scalar arrays ( α i , β i , s ( i ) , r ( i ) ) (\alpha_i, \beta_i, s(i), r(i)) ( α i , β i , s ( i ) , r ( i )) , save two root pointers in each period i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } :
T i r e g T_i^{\mathrm{reg}} T i reg : the root of T T T immediately after Step 5 (RegularClosure( T , α i ) (T,\alpha_i) ( T , α i ) ), representing O i O_i O i on [ 0 , Y i ] [0,Y_i] [ 0 , Y i ] before splitting at d i d_i d i ;
T i d i s c T_i^{\mathrm{disc}} T i disc : the root of X X X immediately after DiscountedRays( X , Q , β i , Y i ) (X,Q,\beta_i,Y_i) ( X , Q , β i , Y i ) in Step 7, representing N i N_i N i on [ 0 , Y i ] [0,Y_i] [ 0 , Y i ] before lower-clipping at d i d_i d i or merge reanchoring, so every surviving bulk record ( F j , V j ) (F_j,V_j) ( F j , V j ) satisfies F j = f j + Q F_j=f_j+Q F j = f j + Q and V j = v j + Q β i V_j=v_j+Q\beta_i V j = v j + Q β i for an original incoming anchor f j < d i f_j<d_i f j < d i .
Lemma 5.1 (Exact virtual predecessors). Fix period i i i and target departure inventory y ∈ [ d i , Y i ] ∩ G y \in[d_i,Y_i]\cap\mathcal{G} y ∈ [ d i , Y i ] ∩ G .
If candidate j = ( f j , v j , π j , t j ) j=(f_j,v_j,\pi_j,t_j) j = ( f j , v j , π j , t j ) in T i r e g T_i^{\mathrm{reg}} T i reg attains O i ( y ) O_i(y) O i ( y ) , then
u = { f j , π j ≥ α i , min { y , t j } , π j < α i , (48) u=\begin{cases}
f_j, & \pi_j\ge\alpha_i,\\
\min\{y,t_j\}, & \pi_j<\alpha_i,
\end{cases} \tag*{(48)} u = { f j , min { y , t j } , π j ≥ α i , π j < α i , (48) satisfies u ∈ [ 0 , K i ] ∩ G u\in[0,K_i]\cap\mathcal{G} u ∈ [ 0 , K i ] ∩ G , u ≤ y u\le y u ≤ y , and O i ( y ) = A i ( u ) + α i ( y − u ) O_i(y)=A_i(u)+\alpha_i(y-u) O i ( y ) = A i ( u ) + α i ( y − u ) .
If N i ( y ) < + ∞ N_i(y)<+\infty N i ( y ) < + ∞ and j j j is the last record in T i d i s c T_i^{\mathrm{disc}} T i disc with F j ≤ y F_j\le y F j ≤ y , then u = F j − Q u=F_j-Q u = F j − Q satisfies u ∈ [ 0 , K i ] ∩ G u\in[0,K_i]\cap\mathcal{G} u ∈ [ 0 , K i ] ∩ G , u < d i u<d_i u < d i , y − u ≥ Q y-u\ge Q y − u ≥ Q , and N i ( y ) = A i ( u ) + β i ( y − u ) N_i(y)=A_i(u)+\beta_i(y-u) N i ( y ) = A i ( u ) + β i ( y − u ) .
Proof. In Claim 1, all anchors and endpoints in T i r e g T_i^{\mathrm{reg}} T i reg originate from A i A_i A i on [ 0 , K i ] [0,K_i] [ 0 , K i ] , so u ∈ [ 0 , K i ] ∩ G u\in[0,K_i]\cap\mathcal{G} u ∈ [ 0 , K i ] ∩ G . By the proof of Lemma 3.3, E j ( y ; α i ) = E j i n ( u ) + α i ( y − u ) E_j(y;\alpha_i)=E_j^{\mathrm{in}}(u)+\alpha_i(y-u) E j ( y ; α i ) = E j in ( u ) + α i ( y − u ) , where E j i n E_j^{\mathrm{in}} E j in is candidate j j j ’s curve in A i A_i A i . Since A i ( u ) ≤ E j i n ( u ) A_i(u)\le E_j^{\mathrm{in}}(u) A i ( u ) ≤ E j in ( u ) , a strict inequality A i ( u ) < E j i n ( u ) A_i(u)<E_j^{\mathrm{in}}(u) A i ( u ) < E j in ( u ) would imply O i ( y ) ≤ A i ( u ) + α i ( y − u ) < E j ( y ; α i ) = O i ( y ) O_i(y)\le A_i(u)+\alpha_i(y-u)<E_j(y;\alpha_i)=O_i(y) O i ( y ) ≤ A i ( u ) + α i ( y − u ) < E j ( y ; α i ) = O i ( y ) , a contradiction (ruling out, in particular, picking an unattained left-limit endpoint at a downward jump). In Claim 2, strictly decreasing intercepts η j = V j − β i F j \eta_j=V_j-\beta_iF_j η j = V j − β i F j imply N i ( y ) = V j + β i ( y − F j ) = v j + β i ( y − u ) N_i(y)=V_j+\beta_i(y-F_j)=v_j+\beta_i(y-u) N i ( y ) = V j + β i ( y − F j ) = v j + β i ( y − u ) at u = F j − Q < d i u=F_j-Q<d_i u = F j − Q < d i ; since A i ( u ) ≤ v j A_i(u)\le v_j A i ( u ) ≤ v j and A i ( u ) < v j A_i(u)<v_j A i ( u ) < v j would strictly lower N i ( y ) N_i(y) N i ( y ) , we have A i ( u ) = v j A_i(u)=v_j A i ( u ) = v j .
Backward virtual backtracking and forward physical routing
Proof of Theorem 1.2. Run the persistent version of Algorithm 4 up to the desired horizon m = n m=n m = n (setting z ⋆ = f j ⋆ z^\star=f_{j^\star} z ⋆ = f j ⋆ , where j ⋆ ∈ T j^\star\in T j ⋆ ∈ T minimizes v j v_j v j and breaks ties toward the smallest anchor f j f_j f j , so z ⋆ < Q z^\star<Q z ⋆ < Q by Theorem 2.7) or m = k m=k m = k (setting z ⋆ = 0 z^\star=0 z ⋆ = 0 for prescribed zero terminal stock). Because Lemma 4.1 and Theorem 1.1 bound the total number of elementary tree searches, splits, joins, and deletions by O ( n ) O(n) O ( n ) , path-copying persistence creates O ( n log n ) O(n\log n) O ( n log n ) node records in O ( n log n ) O(n\log n) O ( n log n ) total forward time and space.
Stage 1 (Virtual backtracking): Starting from I ^ m = z ⋆ \widehat{I}_m=z^\star I m = z ⋆ , iterate i = m , m − 1 , … , 1 i=m,m-1,\ldots,1 i = m , m − 1 , … , 1 . Set y = d i + I ^ i y=d_i+\widehat{I}_i y = d i + I i and evaluate O i ( y ) O_i(y) O i ( y ) on T i r e g T_i^{\mathrm{reg}} T i reg and N i ( y ) N_i(y) N i ( y ) on T i d i s c T_i^{\mathrm{disc}} T i disc in O ( log n ) O(\log n) O ( log n ) time (carrying lazy parameters top-down without mutating saved nodes). Select whichever branch attains F i ( y ) = min { O i ( y ) , N i ( y ) } F_i(y)=\min\{O_i(y),N_i(y)\} F i ( y ) = min { O i ( y ) , N i ( y )} , compute the predecessor u u u via Lemma 5.1, and set q ^ i = y − u \widehat{q}_i=y-u q i = y − u and I ^ i − 1 = u \widehat{I}_{i-1}=u I i − 1 = u . Summing A i + 1 ( I ^ i ) = A i ( I ^ i − 1 ) + κ i + h i I ^ i A_{i+1}(\widehat{I}_i)=A_i(\widehat{I}_{i-1})+\kappa_i+h_i\widehat{I}_i A i + 1 ( I i ) = A i ( I i − 1 ) + κ i + h i I i from i = 1 i=1 i = 1 to m m m (with I ^ 0 = 0 \widehat{I}_0=0 I 0 = 0 ) shows that ( q ^ 1 , … , q ^ m ) (\widehat{q}_1,\ldots,\widehat{q}_m) ( q 1 , … , q m ) is a feasible virtual schedule satisfying ∑ i = 1 m ( κ i + h i I ^ i ) ≤ O P T m \sum_{i=1}^m(\kappa_i+h_i\widehat{I}_i)\le\mathrm{OPT}_m ∑ i = 1 m ( κ i + h i I i ) ≤ OPT m (or O P T m , 0 \mathrm{OPT}_{m,0} OPT m , 0 ), because P ^ i ( q ^ i ) ≤ α i q ^ i \widehat{P}_i(\widehat{q}_i)\le\alpha_i\widehat{q}_i P i ( q i ) ≤ α i q i on regular steps and P ^ i ( q ^ i ) = β i q ^ i \widehat{P}_i(\widehat{q}_i)=\beta_i\widehat{q}_i P i ( q i ) = β i q i on discounted steps ( q ^ i ≥ Q ) (\widehat{q}_i\ge Q) ( q i ≥ Q ) . Stage 1 performs m m m backward steps of O ( log n ) O(\log n) O ( log n ) time each.
Stage 2 (Retroactive origin aggregation): Apply (2.13)–(2.14) of Theorem 2.2 in O ( m ) O(m) O ( m ) time using the saved origin indices ( s ( i ) , r ( i ) ) (s(i),r(i)) ( s ( i ) , r ( i )) , setting q t = ∑ i : q ^ i > 0 , r ( i ) = t q ^ i q_t=\sum_{i:\widehat{q}_i>0,\ r(i)=t}\widehat{q}_i q t = ∑ i : q i > 0 , r ( i ) = t q i for t = 1 , … , m t=1,\ldots,m t = 1 , … , m . By Theorem 2.2, ( q 1 , … , q m ) ∈ G m (q_1,\ldots,q_m)\in\mathcal{G}^m ( q 1 , … , q m ) ∈ G m is physically feasible, satisfies I m = I ^ m I_m=\widehat{I}_m I m = I m (zero when z ⋆ = 0 z^\star=0 z ⋆ = 0 ), and achieves J m ( q , I ) ≤ J ^ m ( q ^ , I ^ ) ≤ O P T m J_m(q,I)\le\widehat{J}_m(\widehat{q},\widehat{I})\le\mathrm{OPT}_m J m ( q , I ) ≤ J m ( q , I ) ≤ OPT m (resp. O P T m , 0 \mathrm{OPT}_{m,0} OPT m , 0 ), so it is an exact physical optimum. Total time and space are O ( n log n ) O(n\log n) O ( n log n ) .
Worked Examples
Speculative forward buying and virtual-to-physical routing
Let Q = 5 Q=5 Q = 5 , n = 3 n=3 n = 3 , holding rates ( h 1 , h 2 , h 3 ) = ( 1 , 1 , 0 ) (h_1,h_2,h_3)=(1,1,0) ( h 1 , h 2 , h 3 ) = ( 1 , 1 , 0 ) , and consider the price-spike instance:
Table 1 (PDF p. 20).
In physical coordinates, period 1 has zero demand (d 1 = 0 = I 0 d_1=0=I_0 d 1 = 0 = I 0 ), yet the unique optimal zero-terminal schedule is q = ( 12 , 0 , 2 ) q=(12,0,2) q = ( 12 , 0 , 2 ) with physical inventories I = ( 0 , 12 , 0 , 0 ) I=(0,12,0,0) I = ( 0 , 12 , 0 , 0 ) and total cost P 1 ( 12 ) + h 1 ( 12 ) + P 2 ( 0 ) + h 2 ( 0 ) + P 3 ( 2 ) = 24 + 12 + 0 + 0 + 6 = 42 P_1(12)+h_1(12)+P_2(0)+h_2(0)+P_3(2)=24+12+0+0+6=42 P 1 ( 12 ) + h 1 ( 12 ) + P 2 ( 0 ) + h 2 ( 0 ) + P 3 ( 2 ) = 24 + 12 + 0 + 0 + 6 = 42 , whereas the unique free-terminal optimum is 41, attained by q = ( 12 , 0 , 5 ) q=(12,0,5) q = ( 12 , 0 , 5 ) ending with I 3 = 3 < Q I_3=3<Q I 3 = 3 < Q at cost 24 + 12 + 5 = 41 24+12+5=41 24 + 12 + 5 = 41 . Notice that in both optimal physical schedules:
q 1 = 12 > 0 q_1=12>0 q 1 = 12 > 0 despite I 0 = 0 ≥ d 1 = 0 I_0=0\ge d_1=0 I 0 = 0 ≥ d 1 = 0 , violating physical zero-inventory ordering;
I 1 = 12 > 2 Q = 10 I_1=12>2Q=10 I 1 = 12 > 2 Q = 10 , violating the 2 Q 2Q 2 Q bound on physical stock (and scaling d 2 d_2 d 2 makes I 1 I_1 I 1 arbitrarily large).
Now trace Algorithm 4 and Theorem 1.2. The online effective prices and origin pointers are:
i = 1 : α 1 = 6 ( s ( 1 ) = 1 ) , β 1 = 2 ( r ( 1 ) = 1 ) ; i = 2 : α 2 = min { 6 + 1 , 25 } = 7 ( s ( 2 ) = 1 ) , β 2 = min { 2 + 1 , 15 } = 3 ( r ( 2 ) = 1 ) ; i = 3 : α 3 = min { 7 + 1 , 3 } = 3 ( s ( 3 ) = 3 ) , β 3 = min { 3 + 1 , 1 } = 1 ( r ( 3 ) = 3 ) . \begin{aligned}
i=1 &: \quad\alpha_1=6\ (s(1)=1), && \beta_1=2\ (r(1)=1);\\
i=2 &: \quad\alpha_2=\min\{6+1,25\}=7\ (s(2)=1), && \beta_2=\min\{2+1,15\}=3\ (r(2)=1);\\
i=3 &: \quad\alpha_3=\min\{7+1,3\}=3\ (s(3)=3), && \beta_3=\min\{3+1,1\}=1\ (r(3)=3).
\end{aligned} i = 1 i = 2 i = 3 : α 1 = 6 ( s ( 1 ) = 1 ) , : α 2 = min { 6 + 1 , 25 } = 7 ( s ( 2 ) = 1 ) , : α 3 = min { 7 + 1 , 3 } = 3 ( s ( 3 ) = 3 ) , β 1 = 2 ( r ( 1 ) = 1 ) ; β 2 = min { 2 + 1 , 15 } = 3 ( r ( 2 ) = 1 ) ; β 3 = min { 3 + 1 , 1 } = 1 ( r ( 3 ) = 3 ) .
At i = 1 i=1 i = 1 , d 1 = 0 d_1=0 d 1 = 0 forbids any auxiliary discounted ray (u < 0 u<0 u < 0 is empty), so F 1 ( y ) = O 1 ( y ) = 6 y F_1(y)=O_1(y)=6y F 1 ( y ) = O 1 ( y ) = 6 y on [ 0 , 10 ] [0,10] [ 0 , 10 ] , Z 1 = F 1 ( 0 ) = 0 Z_1=F_1(0)=0 Z 1 = F 1 ( 0 ) = 0 , and A 2 ( z ) = 7 z A_2(z)=7z A 2 ( z ) = 7 z on [ 0 , 10 ] [0,10] [ 0 , 10 ] . At i = 2 i=2 i = 2 (d 2 = 12 d_2=12 d 2 = 12 , Y 2 = 22 Y_2=22 Y 2 = 22 ), anchor f 1 = 0 < 12 f_1=0<12 f 1 = 0 < 12 generates the discounted ray N 2 ( y ) = 3 y N_2(y)=3y N 2 ( y ) = 3 y on [ 5 , 22 ] [5,22] [ 5 , 22 ] , which dominates O 2 ( y ) = 7 y O_2(y)=7y O 2 ( y ) = 7 y throughout [ 12 , 22 ] [12,22] [ 12 , 22 ] , giving Z 2 = F 2 ( 12 ) = 36 Z_2=F_2(12)=36 Z 2 = F 2 ( 12 ) = 36 and A 3 ( z ) = F 2 ( 12 + z ) + z = 36 + 4 z A_3(z)=F_2(12+z)+z=36+4z A 3 ( z ) = F 2 ( 12 + z ) + z = 36 + 4 z on [ 0 , 10 ] [0,10] [ 0 , 10 ] . At i = 3 i=3 i = 3 (d 3 = 2 d_3=2 d 3 = 2 , Y 3 = 12 Y_3=12 Y 3 = 12 ), lowering the regular comparator from 4 to α 3 = 3 \alpha_3=3 α 3 = 3 yields O 3 ( y ) = 36 + 3 y O_3(y)=36+3y O 3 ( y ) = 36 + 3 y on [ 0 , 12 ] [0,12] [ 0 , 12 ] , while anchor f 1 = 0 < 2 f_1=0<2 f 1 = 0 < 2 generates N 3 ( y ) = 36 + y N_3(y)=36+y N 3 ( y ) = 36 + y on [ 5 , 12 ] [5,12] [ 5 , 12 ] . Thus F 3 ( y ) = 36 + 3 y F_3(y)=36+3y F 3 ( y ) = 36 + 3 y on [ 2 , 5 ) [2,5) [ 2 , 5 ) and F 3 ( y ) = 36 + y F_3(y)=36+y F 3 ( y ) = 36 + y on [ 5 , 12 ] [5,12] [ 5 , 12 ] , recording Z 3 = F 3 ( 2 ) = 42 = O P T 3 , 0 Z_3=F_3(2)=42=\mathrm{OPT}_{3,0} Z 3 = F 3 ( 2 ) = 42 = OPT 3 , 0 . Shifting by d 3 = 2 d_3=2 d 3 = 2 with h 3 = 0 h_3=0 h 3 = 0 leaves two candidates in A 4 A_4 A 4 on [ 0 , 10 ] [0,10] [ 0 , 10 ] with anchor values v 1 = 42 v_1=42 v 1 = 42 (at f 1 = 0 f_1=0 f 1 = 0 ) and v 2 = 41 v_2=41 v 2 = 41 (at f 2 = 3 f_2=3 f 2 = 3 ), yielding O P T = min { 42 , 41 } = 41 \mathrm{OPT}=\min\{42,41\}=41 OPT = min { 42 , 41 } = 41 .
For free-terminal recovery (z ⋆ = 3 z^\star=3 z ⋆ = 3 ): Period 3 (y = 5 y=5 y = 5 ) selects N 3 ( 5 ) = 41 N_3(5)=41 N 3 ( 5 ) = 41 with u = 0 u=0 u = 0 and q ^ 3 = 5 ≥ Q \hat{q}_3=5\ge Q q ^ 3 = 5 ≥ Q ; Period 2 (z = 0 z=0 z = 0 , y = 12 y=12 y = 12 ) selects N 2 ( 12 ) = 36 N_2(12)=36 N 2 ( 12 ) = 36 with u = 0 u=0 u = 0 and q ^ 2 = 12 ≥ Q \hat{q}_2=12\ge Q q ^ 2 = 12 ≥ Q ; Period 1 (z = 0 z=0 z = 0 , y = 0 y=0 y = 0 ) gives q ^ 1 = 0 \hat{q}_1=0 q ^ 1 = 0 . Virtual stock never exceeds z ⋆ = 3 < 2 Q z^\star=3<2Q z ⋆ = 3 < 2 Q . Stage 2 then maps q ^ 2 = 12 \hat{q}_2=12 q ^ 2 = 12 to τ ( 2 ) = r ( 2 ) = 1 \tau(2)=r(2)=1 τ ( 2 ) = r ( 2 ) = 1 and q ^ 3 = 5 \hat{q}_3=5 q ^ 3 = 5 to τ ( 3 ) = r ( 3 ) = 3 \tau(3)=r(3)=3 τ ( 3 ) = r ( 3 ) = 3 , recovering the exact speculative physical plan q = ( 12 , 0 , 5 ) q=(12,0,5) q = ( 12 , 0 , 5 ) of cost 41 (and starting from z ⋆ = 0 z^\star=0 z ⋆ = 0 analogously yields q ^ = ( 0 , 12 , 2 ) \hat{q}=(0,12,2) q ^ = ( 0 , 12 , 2 ) and physical plan q = ( 12 , 0 , 2 ) q=(12,0,2) q = ( 12 , 0 , 2 ) of cost 42).
Positive-state discrepancy and three-regime thresholds
Two further subtleties are shared with the monotone-price auxiliary framework [11 ] and explain our representation choices:
Intermediate positive states need not match unrestricted costs: For Q = 2 Q=2 Q = 2 , h = ( 0 , 0 ) h=(0,0) h = ( 0 , 0 ) , d = ( 1 , 1 ) d=(1,1) d = ( 1 , 1 ) , p 1 , 1 = p 1 , 2 = 5 p_{1,1}=p_{1,2}=5 p 1 , 1 = p 1 , 2 = 5 , and ( p 2 , 1 , p 2 , 2 ) = ( 2 , 1 ) (p_{2,1},p_{2,2})=(2,1) ( p 2 , 1 , p 2 , 2 ) = ( 2 , 1 ) , reaching terminal stock I 2 = 2 I_2=2 I 2 = 2 has true cost 6 via q = ( 2 , 2 ) q=(2,2) q = ( 2 , 2 ) (where I 1 = 1 = d 2 I_1=1=d_2 I 1 = 1 = d 2 ), whereas A 2 ( z ) = 5 ( 1 + z ) A_2(z)=5(1+z) A 2 ( z ) = 5 ( 1 + z ) on [ 0 , 1 ) ∩ G [0,1)\cap\mathcal{G} [ 0 , 1 ) ∩ G and A 2 ( z ) = 2 ( 1 + z ) A_2(z)=2(1+z) A 2 ( z ) = 2 ( 1 + z ) on [ 1 , 4 ] ∩ G [1,4]\cap\mathcal{G} [ 1 , 4 ] ∩ G give O 2 ( 3 ) = A 2 ( 3 ) = 8 O_2(3)=A_2(3)=8 O 2 ( 3 ) = A 2 ( 3 ) = 8 and N 2 ( 3 ) = A 2 ( 0 ) + 3 = 8 N_2(3)=A_2(0)+3=8 N 2 ( 3 ) = A 2 ( 0 ) + 3 = 8 (because the auxiliary recurrence forbids a discounted order from u = 1 = d 2 u=1=d_2 u = 1 = d 2 ), assigning A 3 ( 2 ) = 8 > 6 A_3(2)=8>6 A 3 ( 2 ) = 8 > 6 . Nevertheless, both models have O P T = 4 \mathrm{OPT}=4 OPT = 4 (at I 2 = 0 I_2=0 I 2 = 0 via q = ( 2 , 0 ) q=(2,0) q = ( 2 , 0 ) ) and O P T 2 , 0 = 4 \mathrm{OPT}_{2,0}=4 OPT 2 , 0 = 4 , consistent with Theorem 2.7 .
Anchor secants underestimate domination when a legacy branch exists: Suppose at entry to period 3 (at stored comparator c o l d = 6 c_{\mathrm{old}} = 6 c old = 6 ) a pruned frontier has left candidate ( f L , v L , π L , t L ) = ( 0 , 10 , 2 , 1 ) (f_L, v_L, \pi_L, t_L) = (0, 10, 2, 1) ( f L , v L , π L , t L ) = ( 0 , 10 , 2 , 1 ) and right candidate ( f R , v R , π R , t R ) = ( 2 , 17 , 1 , 2 ) (f_R, v_R, \pi_R, t_R) = (2, 17, 1, 2) ( f R , v R , π R , t R ) = ( 2 , 17 , 1 , 2 ) . The naive anchor secant is ( 17 − 10 ) / ( 2 − 0 ) = 3.5 (17 - 10)/(2 - 0) = 3.5 ( 17 − 10 ) / ( 2 − 0 ) = 3.5 , yet for any comparator c ≥ 2 c \ge2 c ≥ 2 the exact difference in (42) is D ( c ) = 10 + 2 + c − 17 = c − 5 D(c) = 10 + 2 + c - 17 = c - 5 D ( c ) = 10 + 2 + c − 17 = c − 5 , giving θ = 5 \theta= 5 θ = 5 . At α 3 = 4 \alpha_3 = 4 α 3 = 4 , E L ( 2 ; 4 ) = 16 < 17 = E R ( 2 ; 4 ) E_L(2; 4) = 16 < 17 = E_R(2; 4) E L ( 2 ; 4 ) = 16 < 17 = E R ( 2 ; 4 ) , which θ = 5 \theta= 5 θ = 5 detects and the secant 3.5 misses.
Use of AI-Assisted Technologies: Generative AI tools were utilized to enhance clarity, grammar, and overall readability. All core ideas, analyses, and conclusions remain the original work of the author, who has thoroughly reviewed and verified the final text.
Concluding Remarks
We have shown that uncapacitated single-item lot sizing with a stationary one-breakpoint all-units quantity discount, zero setup cost, nonnegative linear holding costs, and arbitrary time-varying prices is solvable in O ( n log n ) O(n \log n) O ( n log n ) time and O ( n ) O(n) O ( n ) working space, matching the classical O ( n log n ) O(n \log n) O ( n log n ) complexity of uncapacitated Wagner–Whitin lot sizing [1 , 12 ] . By reducing arbitrary prices online to non-speculative effective prices ( α i , β i ) (\alpha_i, \beta_i) ( α i , β i ) and reconstructing physical orders via origin pointers ( s ( i ) , r ( i ) ) (s(i), r(i)) ( s ( i ) , r ( i )) , the algorithm avoids maintaining explicit speculative inventory states above 2 Q 2Q 2 Q while remaining exact for both continuous and integral domains.
Two boundaries of the present result merit emphasis. First, the retroactive aggregation in Theorem 2.2 relies on unlimited storage capacity ( B i = + ∞ ) (B_i = +\infty) ( B i = + ∞ ) because routing later virtual orders back to an earlier origin period t = τ ( i ) t = \tau(i) t = τ ( i ) raises intermediate physical inventories I m I_m I m for t ≤ m < i t \le m < i t ≤ m < i as shown in (16) . Notice, however, that our proof of Theorems 2.6 –2.7 and § 4 holds directly whenever raw prices already satisfy the non-speculative conditions p 1 , i + 1 ≤ p 1 , i + h i p_{1,i+1} \le p_{1,i} + h_i p 1 , i + 1 ≤ p 1 , i + h i and p 2 , i + 1 ≤ p 2 , i + h i p_{2,i+1} \le p_{2,i} + h_i p 2 , i + 1 ≤ p 2 , i + h i (even under arbitrary post-order capacities B i ≥ d i B_i \ge d_i B i ≥ d i by setting K i + 1 = min { 2 Q , B i − d i } K_{i+1} = \min\{2Q, B_i - d_i\} K i + 1 = min { 2 Q , B i − d i } , Y i = min { B i , d i + 2 Q } Y_i = \min\{B_i, d_i + 2Q\} Y i = min { B i , d i + 2 Q } , and upper-clipping A i A_i A i to [ 0 , min { K i , Y i } ] [0, \min\{K_i, Y_i\}] [ 0 , min { K i , Y i }] at entry to period i i i , since no origin rerouting is needed when τ ( i ) = i \tau(i) = i τ ( i ) = i ). Extending near-linear algorithms to capacitated instances that combine speculative price spikes ( p 2 , i + 1 > p 2 , i + h i ) (p_{2,i+1} > p_{2,i} + h_i) ( p 2 , i + 1 > p 2 , i + h i ) with fluctuating hard storage bottlenecks remains a distinct structural problem. Second, under an incremental quantity discount (where p 2 , i ≤ p 1 , i p_{2,i} \le p_{1,i} p 2 , i ≤ p 1 , i applies only to units ordered above Q Q Q ), the procurement cost is continuous and piecewise-linear concave rather than discontinuous; investigating whether Ω ( n log n ) \Omega(n \log n) Ω ( n log n ) is a provable algebraic decision-tree lower bound for uncapacitated one-breakpoint all-units lot sizing under arbitrary prices is an appealing question for future work.