betaFeedback

WorksComputer Science

Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds

Abstract

We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring O(n3)O(n^3) arithmetic operations and O(n2)O(n^2) working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of mm positive threshold values, the bounds become Om(nm+2)O_m(n^{m+2}) time and Om(nm+1)O_m(n^{m+1}) space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes O(PW)O(PW) time, where PP is the total number of price tiers and WW is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.

Introduction

An all-units quantity discount applies a lower unit price to an entire order once its quantity reaches a threshold. Unlike an incremental discount, the resulting procurement cost can decrease discontinuously as the order grows. In a multi-period setting, a discount therefore creates a trade-off among ordering more than immediate demand, paying holding costs, and occupying limited storage space. When prices fluctuate over time, the cheapest inventory remaining in a particular policy need not identify the cheapest complete history for another inventory level. Exact methods must compare total costs while preserving both threshold eligibility and the storage constraints of each history.

This paper considers continuous order quantities, nonnegative deterministic demands, linear nonnegative holding costs, and arbitrary finite end-of-period inventory bounds. There are no setup charges, separate production limits, backlogging, or disposal. The entire horizon is known in advance. Our main algorithm does not require either unit-price sequence to be monotone. Its central observation is that an optimal plan can be selected from a finite set of cumulative-purchase levels obtained by translating inventory-bound values by sums of discount thresholds. For one common threshold, this set has O(n2)O(n^2) elements. The apparent quadratic predecessor search in each state then reduces to two prefix minima, giving an O(n3)O(n^3) algorithm.

Related literature and positioning

Dynamic lot sizing has a long algorithmic history beginning with the classical model of Wagner and Whitin [11]. Boundary-based descriptions of optimal production and inventory trajectories appear in Love [4] and Swoveland [10]. Our proof uses this general extreme-point perspective, but expresses it directly in cumulative-purchase coordinates for the stated all-units model.

For piecewise-concave production costs, Koca et al. [3] establish polynomial solvability with a fixed number of common breakpoints, including an O(n2m+3)O(n^{2m+3}) bound for their general no-backlogging formulation. Their extensions also use stock-boundary states. In related piecewise-linear models, Ou [5] obtain an O(nm+2log⁡n)O(n^{m+2}\log n) algorithm, and Papadopoulos [7] report an O(nm+2)O(n^{m+2}) algorithm. The latter work was initially circulated as arXiv:2403.16314 and has since appeared in the Journal of Global Optimization. Thus the exponent m+2m + 2, and polynomial solvability for fixed common breakpoints, are not claimed here to be new in themselves.

Down et al. [1] study a bounded-inventory one-breakpoint special case and give a quadratic algorithm based on a just-in-time structural property. Papadopoulos [8] state an O(nlog⁡n)O(n \log n) algorithm for the one-breakpoint case with non-increasing price sequences and variable inventory capacities. That result is relevant to the conditional certificate in § 6; our main correctness theorem does not rely on it. For broader piecewise-linear production models, Shaw and Wagelmans [9] develop a pseudopolynomial algorithm. This provides context for our lattice implementation, without identifying production-capacity and inventory-capacity formulations.

A recent preprint by Papadopoulos [6] develops Monge matrix searching for nonlinear piecewise-concave production costs, using common production breakpoints and a fixed global collection of stock-boundary levels. The present method instead uses affine tier costs and arbitrary period-specific inventory bounds: their cumulative boundary values contribute only O(n)O(n) anchors, without assuming a fixed number of distinct capacity values. We use elementary prefix minima rather than Monge searching. These differences specify the scope of the contribution; they are not a claim that the present algorithm dominates every algorithm for the broader models.

Results and organization

We give a self-contained critical-state proof, an implementable cubic one-threshold algorithm, and a space-efficient recovery procedure. The proof extends to a fixed global set of threshold values and to unrestricted local thresholds, with explicit accounting for the resulting state-set sizes. A second implementation exploits a manageable inventory lattice. Finally, a historical-price relaxation provides a certified shortcut when a reconstructed plan attains its lower bound. The shortcut is optional, and a rejected certificate leaves the exact dynamic program unchanged.

Section 2 defines the model and its cumulative coordinates. Section 3 proves the cubic result. Section 4 treats multiple and period-dependent thresholds. Section 5 gives the lattice algorithm. Section 6 develops the monotone-relaxation certificate. Section 7 reports reproducible validation and an illustrative timing study. Section 8 discusses scope and further work. Appendix A supplies the full reconstruction argument.

Model and preliminary reductions

Inventory and procurement

There are n≥1n \ge1 periods. Period tt has demand dt≥0d_t \ge0, end-of-period inventory bound Bt≥0B_t \ge0, and holding cost ht≥0h_t \ge0 per unit of ending inventory. All data are finite. An order xt≥0x_t \ge0 and inventory ItI_t satisfy

I0=0,It=It−1+xt−dt,0≤It≤Bt(t=1,…,n).(1)I_0 = 0,\qquad I_t = I_{t-1} + x_t - d_t,\qquad0 \le I_t \le B_t\quad(t = 1,\ldots,n). \tag*{(1)}

For the one-threshold model, Q>0Q > 0 is common to all periods and 0≤p2,t≤p1,t0 \le p_{2,t} \le p_{1,t}. The procurement cost is

ft(x)={p1,tx,0≤x<Q,p2,tx,x≥Q.(2)f_t(x) = \begin{cases} p_{1,t}x, & 0 \le x < Q,\\ p_{2,t}x, & x \ge Q. \end{cases} \tag*{(2)}

Both price sequences are otherwise arbitrary. We minimize

C(x)=∑t=1n(ft(xt)+htIt).(3)C(x) = \sum_{t=1}^{n} \left(f_t(x_t) + h_t I_t\right). \tag*{(3)}

Orders are continuous rather than restricted to integer units. In particular, no rounding of quantities or thresholds is part of the critical-state method.

The bound BtB_t applies after period-tt demand has been met. There is no additional restriction on It−1+xtI_{t-1} + x_t. A model whose post-order inventory cannot exceed TtT_t is obtained by setting Bt=Tt−dtB_t = T_t - d_t, provided Tt≥dtT_t \ge d_t. Conversely, an end-inventory instance can be represented using post-order bounds Tt=Bt+dtT_t = B_t + d_t. An independent upper bound on xtx_t is a different constraint and is not included in the main theorem. We treat two terminal policies: prescribed inventory In=bI_n=b, where 0≤b≤Bn0\le b\le B_n, and free inventory In∈[0,Bn]I_n\in[0,B_n]. These policies cannot be interchanged. For example, with one period, d1=1d_1=1, B1=4B_1=4, Q=4Q=4, prices (10,1)(10,1), and no holding cost, the zero-terminal optimum costs 10, whereas the free-terminal optimum orders four units and costs 4.

Cumulative-purchase coordinates

Define cumulative demand and cumulative purchasing by

D0=Y0=0,Dt=∑s=1tds,Yt=∑s=1txs.(4)D_0=Y_0=0,\qquad D_t=\sum_{s=1}^{t}d_s,\qquad Y_t=\sum_{s=1}^{t}x_s. \tag*{(4)}

Then It=Yt−DtI_t=Y_t-D_t and xt=Yt−Yt−1x_t=Y_t-Y_{t-1}. Feasibility becomes

Y0=0,Yt≥Yt−1,Dt≤Yt≤Dt+Bt.(5)Y_0=0,\qquad Y_t\ge Y_{t-1},\qquad D_t\le Y_t\le D_t+B_t. \tag*{(5)}

Set Ut=Dt+BtU_t=D_t+B_t. Under prescribed terminal inventory, replace UnU_n by Dn+bD_n+b and retain the equality Yn=Dn+bY_n=D_n+b. Under free terminal inventory, no replacement is made. Put

U^t=min⁡s=t,…,nUs,H=U^n,A={0}∪{Dt,U^t:1≤t≤n}.(6)\widehat{U}_t=\min_{s=t,\ldots,n}U_s,\qquad H=\widehat{U}_n,\qquad\mathcal{A}=\{0\}\cup\{D_t,\widehat{U}_t:1\le t\le n\}. \tag*{(6)}

The number of distinct anchors is at most 2n+12n+1.

Lemma 2.1 (Suffix tightening). Replacing the upper bounds in (5) by U^t\widehat{U}_t preserves the set of complete feasible plans, under either terminal policy.

Proof. For s≥ts\ge t, nonnegative orders imply Yt≤Ys≤UsY_t\le Y_s\le U_s. Taking the minimum over ss gives Yt≤U^tY_t\le\widehat{U}_t. Conversely, U^t≤Ut\widehat{U}_t\le U_t, so every trajectory satisfying the tightened bounds satisfies the original ones. The terminal equality, when present, is retained.

All feasible coordinates and anchors lie in [0,H][0,H]. The array U^\widehat{U} is computed by one backward scan. The tightening is a property of complete trajectories, not a capacity allowance for modifying an arbitrary earlier policy. It is legitimate for an offline dynamic program even though some prefixes excluded by the tightening would be feasible in isolation.

Computational model

We count exact arithmetic operations, comparisons, and array accesses. The notation Om(⋅)O_m(\mathord{\cdot}) permits constants depending on a fixed number mm of distinct positive threshold values. It does not denote fixed-parameter tractability, and mm is not allowed to grow silently with nn. For rational inputs, the accompanying implementations use exact fractions; the displayed bounds exclude the bit cost of arithmetic. No constant-time representation or comparison of arbitrary symbolic real expressions is assumed.

A cubic algorithm for one common threshold

An eligible-line representation

The discount discontinuity can be handled without open feasible regions. For every x≥0x \ge0,

ft(x)=min⁡{p1,tx, p2,tx subject to x≥Q}.(7)f_t(x)=\min\{p_{1,t}x,\ p_{2,t}x\text{ subject to }x\ge Q\}. \tag*{(7)}

An ineligible term has value +∞+\infty. The regular-price line may be used above QQ in this representation because it is then dominated by the discounted-price line for the same order. The lower threshold of the latter line cannot be dropped.

For each vector z∈{0,1}nz\in\{0,1\}^{n}, let Pz\mathcal{P}_z be the tightened inventory polytope with additional inequalities

Yt−Yt−1≥ztQ.(8)Y_t-Y_{t-1}\ge z_tQ. \tag*{(8)}

Minimize on Pz\mathcal{P}_z the affine objective

Lz(Y)=∑t=1n[((1−zt)p1,t+ztp2,t)(Yt−Yt−1)+ht(Yt−Dt)].(9)L_z(Y)=\sum_{t=1}^{n}\left[((1-z_t)p_{1,t}+z_tp_{2,t})(Y_t-Y_{t-1})+h_t(Y_t-D_t)\right]. \tag*{(9)}

These polyhedra may overlap. They are used for the proof, not enumerated by the algorithm.

Lemma 3.1 (Affine selection). The original optimum is the minimum of the feasible linear-programming optima min⁡Y∈PzLz(Y)\min_{Y\in\mathcal{P}_z}L_z(Y). An optimal vertex of a best such linear program is an optimum of the original problem.

Proof. For each feasible YY, identity (7) allows a minimizing tier to be selected independently in every period. Hence the pointwise minimum of the eligible affine objectives equals C(x)C(x). There are finitely many tier selections, and every nonempty Pz\mathcal{P}_z is compact because 0≤Yt≤H0\le Y_t\le H. Its affine objective attains a minimum at a vertex. The minimum over all tier selections therefore equals the original optimum. At a minimizing vertex vv of a best selection, C(v)≤Lz(v)=OPTC(v)\le L_z(v)=\mathrm{OPT}; feasibility gives the reverse inequality.

Critical cumulative-purchase levels

Define

V={a+kQ:a∈A, k∈Z, −n≤k≤n}∩[0,H].(10)\mathcal{V}=\{a+kQ:a\in\mathcal{A},\ k\in\mathbb{Z},\ -n\le k\le n\}\cap[0,H]. \tag*{(10)}

After duplicate values are removed, let M=∣V∣M=|\mathcal{V}|. Then M≤(2n+1)2M\le(2n+1)^2.

Theorem 3.2 (One-threshold critical states). Under either terminal policy, there is an optimal plan with Yt∈VY_t\in\mathcal{V} for all t=0,…,nt=0,\ldots,n.

Proof. Choose the optimal vertex supplied by Lemma 3.1. The possible active equalities are

Yt=Dt,Yt=U^t,Yt−Yt−1=0,Yt−Yt−1=Q,(11)Y_t=D_t,\qquad Y_t=\widehat{U}_t,\qquad Y_t-Y_{t-1}=0,\qquad Y_t-Y_{t-1}=Q, \tag*{(11)}

together with the fixed initial coordinate and any prescribed terminal coordinate. The latter equals Un=U^nU_n = \widehat{U}_n and is an anchor.

Consider the path on nodes 0,…,n0,\ldots,n. Retain the edge (t−1,t)(t-1,t) whenever its difference inequality is active. Mark a node as anchored if its coordinate is fixed by an inventory bound, the initial condition, or the terminal equality. Every connected component of retained edges has an anchored node. Otherwise all coordinates in that component could be shifted by the same sufficiently small positive or negative amount. Active difference equalities would remain unchanged, and all remaining inequalities would remain feasible because they have positive slack. This would express the purported vertex as the midpoint of two distinct feasible points.

Starting at an anchored value aa, traverse retained edges to any other node in its component. Each edge changes the coordinate by 00 or QQ. Traversing forward adds these increments; traversing backward subtracts them. The path contains at most nn edges, so the resulting coordinate is a+kQa+kQ with ∣k∣≤n|k| \le n. Feasibility also places it in [0,H][0,H]. □\square

The grid contains exact real quantities determined by the input. Its size does not depend on the numerical magnitude of demand, capacity, or QQ. The theorem does not say that every unrestricted optimal prefix ending at a grid point can be represented on this same grid. Only the existence of a grid-restricted globally optimal complete trajectory is required.

Two prefix minima per layer

Sort the grid as v1<⋯<vMv_1 < \cdots< v_M. Let Gt(v)G_t(v) denote the minimum cost of a path restricted to this grid up to boundary tt, with Yt=vY_t = v. Initialize G0(0)=0G_0(0) = 0 and all other entries to +∞+\infty. For a feasible target Dt≤v≤U^tD_t \le v \le\widehat{U}_t, the Bellman equation is

Gt(v)=ht(v−Dt)+min⁡{p1,tv+min⁡u∈V: u≤v(Gt−1(u)−p1,tu),p2,tv+min⁡u∈V: u≤v−Q(Gt−1(u)−p2,tu)}.(12)G_t(v) = h_t(v-D_t) + \min\left\{ \begin{aligned} &p_{1,t}v + \min_{u\in V:\,u\le v}\left(G_{t-1}(u)-p_{1,t}u\right),\\ &p_{2,t}v + \min_{u\in V:\,u\le v-Q}\left(G_{t-1}(u)-p_{2,t}u\right) \end{aligned} \right\}. \tag*{(12)}

Set Gt(v)=+∞G_t(v) = +\infty outside the feasible band. The first term permits all nonnegative order quantities; the second requires an order of at least QQ. Their minimum is the exact all-units cost by (7).

For the first term, scan targets in increasing order and maintain the smallest value of Gt−1(u)−p1,tuG_{t-1}(u)-p_{1,t}u in the prefix u≤vu\le v. For the second, advance a pointer through the prefix u≤v−Qu\le v-Q and maintain the corresponding minimum. Each predecessor enters each prefix once. Both scans read the same frozen previous layer; they do not use values computed earlier in the current layer. Hence one period costs O(M)O(M) time and two arrays suffice for objective computation.

Theorem 3.3 (Cubic one-threshold algorithm). The one-common-threshold problem with arbitrary temporal prices and variable end-inventory bounds can be solved exactly in O(n3)O(n^3) arithmetic operations and O(n2)O(n^2) working space. These bounds include recovery of an optimal purchase plan.

Proof. The Bellman equation compares all feasible grid predecessors and charges exact procurement and holding costs. It therefore computes the optimum among grid-restricted paths. For prescribed terminal inventory, return Gn(Dn+b)G_n(D_n+b); for free terminal inventory, return min⁡v∈VGn(v)\min_{v\in V}G_n(v). Theorem 3.2 shows that this final value equals the unrestricted optimum.

Constructing and sorting (10) takes O(n2log⁡(n+1))O(n^2\log(n+1)) operations and O(n2)O(n^2) space. The nn layers require O(nM)=O(n3)O(nM)=O(n^3) operations and O(M)O(M) space. Appendix A proves that a forward–backward midpoint reconstruction takes O(nM)O(nM) further operations and O(M+n)O(M+n) space for two tiers. Its additional time and space fit within the displayed bounds. □

A small instance

Consider Q=4Q=4, zero holding costs, and the data in Table 1, with I3=0I_3=0.

ttdtd_tBtB_tp1,tp_{1,t}p2,tp_{2,t}xt∗x_t^*It∗I_t^*
1145154
22810302
3485420

Table 1. An arbitrary-price instance with an optimal cost of 15.

The optimal cumulative coordinates are (Y1,Y2,Y3)=(5,5,7)(Y_1,Y_2,Y_3)=(5,5,7). Here D=(1,3,7)D=(1,3,7) and the tightened upper bounds are (5,7,7)(5,7,7), so these coordinates belong to the critical grid. The first order uses the first-period discount, while the last order uses the regular tier. Neither sorting periods by price nor comparing only the price of surviving inventory describes this policy. Equation (12) evaluates complete histories and their capacities instead.

Multiple and period-dependent thresholds

General all-units pricing

In period tt, let

0=qt,0<qt,1<⋯<qt,mt<qt,mt+1=+∞,pt,0≥⋯≥pt,mt≥0.(13)0=q_{t,0}<q_{t,1}<\cdots<q_{t,m_t}<q_{t,m_t+1}=+\infty,\qquad p_{t,0}\ge\cdots\ge p_{t,m_t}\ge0. \tag*{(13)}

The cost is ft(x)=pt,kxf_t(x)=p_{t,k}x for qt,k≤x<qt,k+1q_{t,k}\le x<q_{t,k+1}. Equality at a threshold receives the newly eligible lower price. Prices are non-increasing with quantity within each period, but are unrestricted over time. Define the total tier count and maximum local count by

P=∑t=1n(mt+1),Kmax⁡=max⁡t(mt+1).(14)P = \sum_{t=1}^{n}(m_t + 1), \qquad K_{\max} = \max_t(m_t + 1). \tag*{(14)}

The one-threshold model is recovered by mt=1m_t = 1 and qt,1=Qq_{t,1} = Q, with pt,0=p1,tp_{t,0} = p_{1,t} and pt,1=p2,tp_{t,1} = p_{2,t}.

The eligible-line representation generalizes to

ft(x)=min⁡k:qt,k≤xpt,kx.(15)f_t(x) = \min_{k: q_{t,k}\le x} p_{t,k}x. \tag*{(15)}

The largest eligible index has a weakly smaller unit price than all previous ones. Accordingly, every line can extend past its nominal upper endpoint, but its lower eligibility threshold must remain.

A critical grid for local thresholds

Retain DD, U^\widehat{U}, HH, and A\mathcal{A} from § 2. Define

S={∑t=1nzt:zt∈{0,qt,1,…,qt,mt}}∩[0,H],(16)\mathcal{S} = \left\{ \sum_{t=1}^{n} z_t : z_t \in\{0,q_{t,1},\ldots,q_{t,m_t}\} \right\} \cap[0,H], \tag*{(16)}
V={a+s,a−s:a∈A, s∈S}∩[0,H].(17)\mathcal{V} = \{a+s, a-s : a \in\mathcal{A},\ s \in\mathcal{S}\} \cap[0,H]. \tag*{(17)}

Write R=∣S∣R = |\mathcal{S}| and M=∣V∣M = |\mathcal{V}|. Notice that R≤MR \le M because 00 is an anchor and every s∈Ss \in\mathcal{S} is a grid point. Also, M≤2(2n+1)RM \le2(2n+1)R.

Theorem 4.1 (Multi-threshold critical states). Under either terminal policy, there is an optimal plan whose cumulative purchases all belong to (17).

Proof. For each tier selection (k1,…,kn)(k_1,\ldots,k_n), minimize the affine objective

∑t=1n[pt,kt(Yt−Yt−1)+ht(Yt−Dt)]\sum_{t=1}^{n} [p_{t,k_t}(Y_t-Y_{t-1}) + h_t(Y_t-D_t)]

on the tightened inventory polytope with additional inequalities Yt−Yt−1≥qt,ktY_t-Y_{t-1} \ge q_{t,k_t}. Identity (15) and the argument of Lemma 3.1 give a globally optimal vertex of a best selection.

Retain active edges (t−1,t)(t-1,t) exactly as in Theorem 3.2. Their increments are now the selected local thresholds, including zero. Every retained-edge component has an anchor. A path from an anchor to a coordinate adds, or subtracts, at most one local threshold from each intervening period. Choose zero in every other period. The resulting sum belongs to the untruncated set in (16). Both the anchor and the coordinate lie in [0,H][0,H], so their distance is at most HH; the sum is therefore retained in S\mathcal{S}.

The use of a+sa+s and a−sa-s, rather than arbitrary signed sums, follows from the path geometry: all edges on a path from one time to another are traversed in the same temporal direction. The local-choice construction also avoids allowing a single period to contribute two distinct thresholds. It may still retain many values that are unnecessary for a particular instance, but it is guaranteed not to exclude every optimal plan.

Tierwise prefix-minimum dynamic programming

For each feasible target Dt≤v≤U^tD_t \le v \le\widehat{U}_t,

Gt(v)=ht(v−Dt)+min⁡0≤k≤mt{pt,kv+min⁡u∈V:u≤v−qt,k(Gt−1(u)−pt,ku)}.(18)G_t(v) = h_t(v-D_t) + \min_{0 \le k \le m_t} \left\{p_{t,k}v + \min_{\substack{u \in V:\\u\le v-q_{t,k}}} \left(G_{t-1}(u)-p_{t,k}u\right)\right\}. \tag*{(18)}

The initialization and terminal selection are unchanged. Every tier requires one prefix-minimum scan; there is no optimization over the nominal upper endpoint of that tier. The total time for value layers is O(PM)O(PM) once the grid is sorted.

Algorithm 1 One period of the critical-grid dynamic program

Require: Sorted grid v1<⋯<vMv_1 < \cdots< v_M; previous values A1,…,AMA_1,\ldots,A_M; period tt

Ensure: Current values C1,…,CMC_1,\ldots,C_M

  1. Ci←+∞C_i \leftarrow+\infty for all ii

  2. for k=0,…,mtk = 0,\ldots,m_t do

  3. j←1j \leftarrow1; β←+∞\beta\leftarrow+\infty

  4. for i=1,…,Mi = 1,\ldots,M do

  5. while j≤Mj \le M and vj≤vi−qt,kv_j \le v_i-q_{t,k} do

  6. β←min⁡{β,Aj−pt,kvj}\beta\leftarrow\min\{\beta,A_j-p_{t,k}v_j\}

  7. j←j+1j \leftarrow j+1

  8. end while

  9. Ci←min⁡{Ci,pt,kvi+β}C_i \leftarrow\min\{C_i,p_{t,k}v_i+\beta\}

  10. end for

  11. end for

  12. for i=1,…,Mi = 1,\ldots,M do

  13. if Dt≤vi≤U^tD_t \le v_i \le\widehat{U}_t then

  14. Ci←Ci+ht(vi−Dt)C_i \leftarrow C_i+h_t(v_i-D_t)

  15. else

  16. Ci←+∞C_i \leftarrow+\infty

  17. end if

  18. end for

Proposition 4.2 (Correctness on the finite grid). Algorithm 1, applied successively with (17), returns the unrestricted global optimum under the specified terminal policy.

Proof. For fixed predecessor uu and target vv, xt=v−u≥qt,kx_t=v-u\ge q_{t,k} is equivalent to u≤v−qt,ku\le v-q_{t,k}. Minimizing over eligible tiers gives ft(v−u)f_t(v-u) exactly. Therefore (18) is the ordinary shortest-path recurrence on the layered grid. Its final value is the restricted optimum. Theorem 4.1 supplies an unrestricted optimum on that grid. Conversely, every grid trajectory satisfies the original balance and inventory constraints, so the restricted optimum cannot be smaller.

Constructing the grid and bounding the running time

The sum set is generated recursively from S(0)={0}\mathcal{S}^{(0)} = \{0\}:

S(t)=⋃q∈{0,qt,1,…,qt,mt}(S(t−1)+q)∩[0,H].(19)\mathcal{S}^{(t)} = \bigcup_{q \in\{0,q_{t,1},\ldots,q_{t,m_t}\}} \left(\mathcal{S}^{(t-1)} + q\right) \cap[0,H]. \tag*{(19)}

Every offset is nonnegative. Once a partial sum exceeds HH, it can never contribute to a retained final sum, so clipping is exact. Each stage merges at most Kmax⁡K_{\max} sorted translated lists and removes duplicates. Since zero is always an option, every retained partial sum remains in the final set, and each partial set has size at most RR. A standard heap-based multiway merge therefore constructs S\mathcal{S} in O(PRlog⁡(Kmax⁡+1))O(PR\log(K_{\max}+1)) operations.

For each anchor, the lists of feasible a+sa+s values and of feasible a−sa-s values, with the latter traversed in reverse sum order, are sorted. Merging these O(n)O(n) lists takes O(nRlog⁡(n+1))O(nR\log(n+1)) operations. This construction uses comparisons rather than an assumed constant-time hashing operation.

Theorem 4.3 (General instance-dependent bounds). For arbitrary local thresholds, the optimal value can be computed in

O(PRlog⁡(Kmax⁡+1)+nRlog⁡(n+1)+PM)(20)O\left(PR\log(K_{\max}+1)+nR\log(n+1)+PM\right) \tag*{(20)}

operations. Working space, excluding input storage, is O(M+n)O(M+n). An optimal plan can be recovered within the same working-space bound using at most O(nKmax⁡M)O(nK_{\max}M) additional operations.

Proof. The preceding merges account for preprocessing. The value layers account for PMPM operations. The sum and grid arrays, merge heaps, and two value layers occupy O(M+n)O(M+n) space because R≤MR \le M; moreover Kmax⁡≤R+1K_{\max} \le R+1 after irrelevant thresholds above HH are ignored. Processing the original input costs O(P)O(P), which is already covered. The reconstruction bounds follow from Appendix A.

Suppose now that every positive threshold belongs to a fixed global set {Q1,…,Qm}\{Q_1,\ldots,Q_m\}. Periods may use different subsets of this set. Every sum in (16) has the form

∑r=1mkrQr,kr∈Z≥0,∑r=1mkr≤n.(21)\sum_{r=1}^{m} k_r Q_r,\qquad k_r \in\mathbb{Z}_{\ge0},\qquad\sum_{r=1}^{m} k_r \le n. \tag*{(21)}

Counting the nonnegative integer vectors yields

R≤(n+mm),M≤2(2n+1)(n+mm).(22)R \le\binom{n+m}{m},\qquad M \le2(2n+1)\binom{n+m}{m}. \tag*{(22)}

Different vectors may yield the same sum; the algorithm removes such coincidences rather than counting them as different states.

Corollary 4.4 (Fixed global threshold set). For fixed m≥1m \ge1, the problem with arbitrary temporal prices and arbitrary period-specific inventory bounds is solvable in Om(nm+2)O_m(n^{m+2}) arithmetic operations and Om(nm+1)O_m(n^{m+1}) working space, including an optimal plan.

Proof. For fixed mm, R=Om(nm)R = O_m(n^m), M=Om(nm+1)M = O_m(n^{m+1}), P≤(m+1)nP \le(m + 1)n, and Kmax⁡≤m+1K_{\max} \le m + 1. Substitute these inequalities in Theorem 4.3. The grid-construction term Om(nm+1log⁡(n+1))O_m(n^{m+1}\log(n + 1)) is dominated by Om(nm+2)O_m(n^{m+2}).

Global threshold valuesArithmetic timeWorking space
One common thresholdO(n3)O(n^3)O(n2)O(n^2)
Two distinct valuesO(n4)O(n^4)O(n3)O(n^3)
Three distinct valuesO(n5)O(n^5)O(n4)O(n^4)
Fixed mm valuesOm(nm+2)O_m(n^{m+2})Om(nm+1)O_m(n^{m+1})

Table 2. Bounds for a fixed global set of positive threshold values. Working space includes plan recovery but excludes input storage and bit costs.

Why a local tier bound is not a global breakpoint bound

With unrestricted period-dependent thresholds, only

R≤∏t=1n(mt+1)(23)R \le\prod_{t=1}^{n}(m_t + 1) \tag*{(23)}

is guaranteed. Even one positive threshold per period can produce an exponential set: choose qt,1=2t−1q_{t,1} = 2^{t-1} and a final feasible cumulative range containing [0,2n−1][0, 2^n - 1]. All 2n2^n subset sums are distinct and survive the truncation. This situation can occur, for example, when a final demand of 2n−12^n - 1 is preceded by zero demands and sufficiently large inventory bounds. The example establishes exponential growth of this construction, not NP-hardness of the exact restricted model.

Thus a bound on mtm_t in every period does not justify treating mm as a fixed constant in Corollary 4.4. Conversely, local thresholds drawn from a fixed global set satisfy that corollary even when each period uses a different subset. The distinction concerns threshold values, not the number of rows in a price table.

An inventory-lattice implementation

Suppose demands, inventory bounds, all positive thresholds, and prescribed terminal inventory are integer multiples of some δ>0\delta> 0. Unit prices and holding costs need not be multiples of δ\delta.

Corollary 5.1 (Existence of a lattice optimum). Under these assumptions, there is an optimal plan whose purchases and inventories are all in δZ\delta\mathbb{Z}.

Proof. Every cumulative-demand value, tightened upper bound, and anchor is a multiple of δ\delta. Every local-choice sum is also such a multiple. Theorem 4.1 therefore gives a cumulative-purchase trajectory on this lattice. Differences give lattice purchases and inventories.

Let Ft(i)F_t(i) be the best cost for end inventory i∈{0,δ,2δ,…,Bt}i \in\{0,\delta,2\delta,\ldots,B_t\}. The initialization is F0(0)=0F_0(0)=0. For every feasible lattice target ii,

Ft(i)=hti+min⁡k{pt,k(dt+i)+min⁡u∈{0,δ,…,Bt−1}u≤dt+i−qt,k(Ft−1(u)−pt,ku)}.(24)F_t(i)=h_ti+\min_k\left\{p_{t,k}(d_t+i)+\min_{\substack{u\in\{0,\delta,\ldots,B_{t-1}\}\\u\le d_t+i-q_{t,k}}}\left(F_{t-1}(u)-p_{t,k}u\right)\right\}. \tag*{(24)}

where at t=1t=1 the predecessor set consists only of zero. The condition inside the minimum is precisely the tier eligibility condition for xt=dt+i−ux_t=d_t+i-u. Every tier again uses an expanding prefix.

Proposition 5.2 (Lattice complexity). With W=1+max⁡tBt/δW=1+\max_t B_t/\delta, the optimal value can be computed in O(PW)O(PW) operations and O(W)O(W) working space. Storing one predecessor per state yields an optimal plan with O(nW)O(nW) working space.

Proof. Every previous and current inventory layer has at most WW states. A tier scans both layers once, giving O(W)O(W) work, and the total tier count is PP. Corollary 5.1 makes the final lattice optimum exact. Predecessor indices give the stated direct recovery bound.

This is a pseudopolynomial result: WW can be exponentially large in the binary input length. It is nevertheless useful when stock capacities are moderate in natural units. Choosing a coarser δ\delta without checking that all flow data are its multiples would invalidate the exactness claim. The code raises an error rather than silently rounding incompatible data. Unlike the cumulative coordinate, physical inventory need not be monotone; we do not transfer the width-partition argument of Appendix A to this lattice implementation.

A certificate from a monotone relaxation

The cubic and fixed-mm algorithms are self-contained. An optional shortcut can exploit a solver for a more structured relaxation. Throughout this section, a monotone oracle means an exact solver returning an optimal purchase plan for the one-common-threshold model with non-increasing unit prices, zero holding costs, and the specified inventory bounds. If this oracle has O(nlog⁡n)O(n\log n) arithmetic complexity, as stated in [8], the accepted shortcut inherits that complexity. This conditional use does not assume that the oracle can process an arbitrary incoming value function or historical state updates.

Removing holding costs and taking historical minima

For the one-threshold instance, put

ηt=∑r=tnhr,cα,t=pα,t+ηt,K=∑t=1nhtDt(α=1,2).(25)\eta_t = \sum_{r=t}^{n} h_r,\qquad c_{\alpha,t}=p_{\alpha,t}+\eta_t,\qquad K=\sum_{t=1}^{n}h_tD_t\quad(\alpha=1,2). \tag*{(25)}

Using It=∑s≤txs−DtI_t=\sum_{s\le t}x_s-D_t gives

∑t(ft(xt)+htIt)=∑tf~t(xt)−K,(26)\sum_t\left(f_t(x_t)+h_tI_t\right)=\sum_t\widetilde{f}_t(x_t)-K, \tag*{(26)}

where f~t\widetilde{f}_t has the same threshold and unit prices c1,t,c2,tc_{1,t},c_{2,t}. Now define

cˉα,t=min⁡j≤tcα,j,(27)\bar{c}_{\alpha,t}=\min_{j\le t}c_{\alpha,j}, \tag*{(27)}

and record the latest index jα,tj_{\alpha,t} attaining each minimum. The two sequences cˉα,t\bar{c}_{\alpha,t} are non-increasing, with cˉ2,t≤cˉ1,t\bar{c}_{2,t}\le\bar{c}_{1,t}. Replacing cc by cˉ\bar{c} and setting holding costs to zero relaxes the objective while retaining the feasible set. If its optimal purchase cost is R∗R^*, then

L=R∗−K≤OPT.(28)L=R^*-K\le\mathrm{OPT}. \tag*{(28)}

Whole-order reconstruction

Let ztz_t be an optimal relaxed order, and let αt=1\alpha_t=1 if zt<Qz_t<Q and αt=2\alpha_t=2 otherwise. Move each whole order to its recorded source:

xj′=∑t:jαt,t=jzt.(29)x'_j=\sum_{t:j_{\alpha_t,t}=j}z_t. \tag*{(29)}

Whole orders, rather than arbitrary fractions of discounted orders, are moved so that the common threshold remains satisfied at the source.

Lemma 6.1 (Cost of merging orders). An all-units procurement cost with non-increasing unit prices satisfies f(a+b)≤f(a)+f(b)f(a+b)\le f(a)+f(b) for all a,b≥0a,b\ge0. The same statement holds after adding a nonnegative linear holding adjustment to every tier price.

Proof. For positive aa and bb, the unit price at quantity a+ba+b is no greater than the unit price at either constituent quantity. Multiplication by aa and bb and addition gives the inequality. If one quantity is zero, the claim follows from f(0)=0f(0)=0. Adding a linear term preserves it.

The adjusted source cost of each moved order is its relaxed cost. Merging orders at one source cannot increase that sum by Lemma 6.1. (26) then gives C(x′)≤LC(x')\le L, where the expression CC can be evaluated even before capacity feasibility is checked. Purchases only move backward, so

∑j≤txj′≥∑j≤tzj≥Dt.(30)\sum_{j\le t} x'_j \ge\sum_{j\le t} z_j \ge D_t. \tag*{(30)}

Total purchasing is unchanged. Thus shortages cannot be introduced and terminal inventory is preserved, but an intermediate upper inventory bound may be violated.

Theorem 6.2 (One-threshold certificate). If the reconstructed plan in (29) satisfies ∑j≤txj′−Dt≤Bt\sum_{j\le t} x'_j-D_t \le B_t for every tt, it is globally optimal. The certificate requires one monotone-oracle call and O(n)O(n) additional operations.

Proof. The reconstruction is feasible by the capacity test, (30), and preservation of terminal inventory. Therefore

L≤OPT≤C(x′)≤L,L \le\mathrm{OPT} \le C(x') \le L,

so equality holds throughout. Prefix minima, source assignment, cumulative inventory, and the capacity test all require linear time.

For already non-increasing original prices and nonnegative holding costs, cα,tc_{\alpha,t} is also non-increasing. Choosing the latest minimizer yields jα,t=tj_{\alpha,t}=t, so the certificate succeeds without moving any order. For genuinely unlimited storage and prescribed terminal inventory, every backward move is feasible and the certificate again succeeds. One can represent this case with the redundant cumulative-purchase bound Yt≤Dn+bY_t\le D_n+b before calling a finite-bound oracle.

With finite capacities, acceptance is not guaranteed. For example, take Q=4Q=4, d=(1,4)d=(1,4), B=(1,4)B=(1,4), prices p1=(2,8)p_1=(2,8) and p2=(1,4)p_2=(1,4), no holding cost, and zero terminal inventory. The relaxation orders (1,4)(1,4) at cost 6. Moving both orders to period 1 produces (5,0)(5,0), whose first ending inventory is 4>B14>B_1. The original optimum costs 18. A rejected reconstruction does not imply that every possible reconstruction fails, or that the relaxation necessarily has a strict optimality gap.

Terminal policies and the oracle interface

A zero-terminal oracle suffices. For prescribed In=bI_n=b, replace the last relaxed demand by dn+bd_n+b and its final end-inventory bound by zero. Order quantities and relaxed purchasing costs are unchanged under this mapping. For free terminal inventory, append a period with demand BnB_n, zero prices, zero holding cost, and zero ending inventory. Any admissible original terminal inventory is completed by a free purchase. Appending zero prices preserves monotonicity. Discard that dummy purchase after the oracle call. These operations are applied to the zero-holding relaxation; the constant KK in (25) still refers to the original periods.

A one-threshold certificate for multi-threshold instances

When positive thresholds exist, let Q∗=min⁡t,k≥1qt,kQ_* = \min_{t,k \ge1} q_{t,k} and define

gt(x)={pt,0x,x<Q∗,pt,mtx,x≥Q∗.(31)g_t(x) = \begin{cases} p_{t,0}x, & x < Q_*, \\ p_{t,m_t}x, & x \ge Q_*. \end{cases} \tag*{(31)}

Then gt(x)≤ft(x)g_t(x) \le f_t(x): below Q∗Q_* no positive threshold has been reached, and above it the surrogate uses the lowest local price, possibly too early. If there are no positive thresholds, use identical tier prices and any positive Q∗Q_*. Applying (25)–(27) to this surrogate yields another monotone one-threshold relaxation and a lower bound LL.

Reconstruct whole orders as before, but evaluate the candidate with the original thresholds. Capacity feasibility alone is no longer sufficient. The appropriate acceptance test is

x′ satisfies all original constraints,C(x′)=L.(32)x' \text{ satisfies all original constraints}, \qquad C(x') = L. \tag*{(32)}

Whenever (32) holds, L≤OPT≤C(x′)=LL \le\mathrm{OPT} \le C(x') = L proves optimality. With an O(nlog⁡n)O(n \log n) oracle, this attempted certificate takes O(P+nlog⁡n)O(P + n \log n) operations, including reading and evaluating the tier data.

The extra cost test is essential. With two periods, d=(0,2)d = (0,2), B=(10,10)B = (10,10), zero holding and terminal inventory, take local thresholds (10,2)(10,2) and price pairs ((10,1),(9,2))((10,1),(9,2)). The surrogate relaxation has value 2. Its two-unit order can be moved to period 1 without exceeding capacity, but it does not reach that period’s true threshold of ten. The actual reconstructed cost is 20, while the original optimum costs 4. The full test correctly rejects this candidate.

The complete certified procedure tries the relaxation, returns a candidate only when its appropriate certificate succeeds, and otherwise invokes the critical-grid or lattice algorithm. All worst-case bounds for the fallback remain unchanged. No unconditional near-linear algorithm is asserted for arbitrary temporal prices or multiple thresholds.

Implementation and computational validation

Reference implementations and reproducibility

The supplementary package contains exact-rational Python implementations of the one-threshold and multi-threshold critical-grid algorithms. The multi-threshold implementation also provides the lattice algorithm and an optional certificate wrapper. Rational data are represented by fractions.Fraction. Threshold equality is resolved by selecting the newly eligible lower tier. Grid and sum-set duplicates are removed by sorted merging. An explicit state-count guard raises an exception if its user-selected limit is exceeded; it never silently truncates the grid or returns an approximate answer.

The critical-grid code computes a value using two layers and reconstructs orders by the midpoint procedure of Appendix A. Every recovered plan is checked against the original inventory balances, bounds, terminal policy, and objective. The lattice implementation uses ordinary predecessor tables for plan recovery. The code does not include the augmented-tree monotone algorithm: certificate tests use the exact cubic implementation as a reference oracle. Consequently these tests validate the reduction and certificate, not a near-linear implementation.

The results below were regenerated from the supplied scripts for this manuscript. The package records pseudorandom seeds, generators, exact inputs for the timing study, per-instance median timing records, machine-readable reports, and environment information. Python 3.13.5 and SciPy 1.17.0 were used; SciPy is required only for the independent linear-programming checks.

Exact-answer checks

We used two independently expressed comparison methods. First, an exhaustive inventory-state dynamic program enumerates every feasible predecessor on the specified small flow lattice and evaluates the actual all-units cost. It does not use critical-state pruning or tierwise prefix minima. Second, a tier-enumeration procedure solves one linear program for every choice of actual tier intervals on small rational instances. Its variables are order quantities, with cumulative inventory constraints. Tier intervals are closed for these checks: closing an earlier tier at its upper threshold can only overcharge the true lower cost there, while the correct adjacent tier is separately enumerated. The minimum over all selections is thus unchanged. This comparison does not use the critical grid.

CheckOne thresholdMultiple/local thresholds
Integer-flow cases versus exhaustive inventory DP1,0001,000
Rational-lattice cases versus exhaustive inventory DP333500
Compatibility with one-threshold implementation—100
Certificate/fallback cases versus exact solver333200
Monotone cases with required certificate acceptance100—
Rational cases versus tier-enumeration LPs10060
Tier assignments enumerated in those LP tests2,036658
Named regression checks66

Table 3. Regenerated validation checks. Counts describe tests, not claims that every randomly generated instance is distinct.

All exact-answer comparisons passed. All lattice instances in the multi-threshold suite were also solved by both value-only and plan-recovering variants of the lattice solver. The one-threshold suite uses seed 251011368, and the multi-threshold suite uses seed 2510113682026. The latter includes shared and period-specific thresholds, zero-price ties, zero demands and capacities, and both prescribed and free terminal inventory. The rational LP tests use independently generated fractions rather than only rescaled integer instances. Their tolerance is 10−7max⁡{1,∣LP objective∣}10^{-7}\max\{1,|\mathrm{LP\ objective}|\}; all other objective comparisons use exact rational equality. Complete parameter ranges appear in the scripts and supplementary notes.

Of the 333 one-threshold certificate cases, 222 were accepted and 111 were rejected; all 100 separately generated monotone cases were accepted. Of the 200 multi-threshold certificate cases, 64 were accepted and 136 were rejected. Ninety-one of those rejections occurred without a capacity violation, illustrating that objective equality under the original tiers is an independent requirement. These are frequencies for the stated small-instance generators, not estimates of acceptance rates in operational data. Finite tests supplement, rather than replace, the proofs.

An illustrative comparison of the two implementations

A separate synthetic timing study compares objective-only critical-grid and inventory-lattice solves. It uses n∈{20,40,80}n \in\{20,40,80\}, m∈{1,2,3}m \in\{1,2,3\}, and three replications per combination of horizon, breakpoint count, and capacity regime, giving 54 instances. The common thresholds are the first mm values of (7, 13, 23). Demands are independent integers from 1 to 8; prices are independent integers from 1 to 30, sorted within each period; and holding costs are integers from 0 to 3. Tight capacities are integers from 0 to 6 and wide capacities from 15 to 30. Terminal inventory is zero. The pseudorandom seed is 20261015.

Each implementation is timed three times per instance after a warm-up; method order alternates and the median elapsed time is retained. Timing includes critical-grid construction where applicable, but excludes instance generation, imports, and plan recovery. The tables aggregate those per-instance medians geometrically. Both methods use the same exact-arithmetic representation, and all 54 pairs of objective values agree exactly.

mmCapacityMM rangeWmax⁡W_{\max}Grid (s)Lattice (s)Ratio
1Tight74–39670.05050.001828.34
1Wide70–381310.05880.01224.82
2Tight74–37570.13660.002068.73
2Wide99–385310.15480.014810.48
3Tight68–38470.17820.002090.16
3Wide67–386310.20470.017211.87

Table 4. Illustrative objective-only timings on 54 integer-flow instances. Each row pools nine instances; times are geometric means of per-instance median seconds. The ratio is critical-grid time divided by lattice time.

The run used Python 3.13.5 on Linux x86_64 with an Intel Xeon Platinum 8370C processor (2.80 GHz, shared container). The archived environment records the exact versions and per-instance timing records.

The experiment deliberately includes moderate integer storage capacities, so the inventory-lattice width is small. It illustrates an implementation choice rather than a claim of universal superiority of the critical grid. On these data, repeated threshold sums coalesce; the experiment therefore does not probe the worst-case nm+1n^{m+1} growth of the critical-state set. The code is a transparent Python reference implementation, not an optimized solver, and shared-container timings should not be interpreted as stable hardware performance estimates. No published implementation, commercial mixed-integer optimizer, or near-linear oracle is benchmarked.

Discussion and conclusions

For one common all-units threshold, arbitrary time-dependent prices can be handled by an exact cubic dynamic program with quadratic working space. The method uses a finite set of cumulative-purchase states supported by an extreme-point argument and evaluates each period with two prefix minima. It neither assumes continuity at a discount threshold nor permanently prunes an inventory history from a comparison of marginal prices alone. Arbitrary end-of-period bounds contribute a linear number of anchors.

With a fixed global set of mm threshold values, the same construction gives Om(nm+2)O_m(n^{m+2}) time and Om(nm+1)O_m(n^{m+1}) working space, including a purchase plan. This supplies a direct all-units implementation within the family of known fixed-breakpoint polynomial bounds, not a priority claim for the exponent. For unrestricted local thresholds, the method remains exact but its sum set may be exponential. A bounded local tier count alone does not remove this limitation. For moderate commensurate inventories, a pseudopolynomial lattice implementation can be preferable.

The monotone-price relaxation provides an additional, logically separate tool. It is useful whenever a reconstructed plan attains the relaxation’s lower bound, but its acceptance cannot be assumed with finite storage or coarsened thresholds. The exact fallback provides the worst-case guarantee. The reproducible computational checks support the implementations without turning a conditional shortcut into an unconditional complexity result.

Several questions remain. Tighter critical-state sets may improve the practical range of the fixed-mm method, and a smaller worst-case bound may be possible for the one-threshold arbitrary-price case. Unrestricted period-dependent thresholds require either a different polynomial-size representation or a separate complexity classification; exponential subset sums alone are not such a classification. Independent order limits, setup charges, backlogging, and nonlinear holding costs change the model and would require new statements and proofs rather than an automatic reuse of the bounds reported here.

Data and code availability

The Python source, synthetic instance generators, exact timing inputs, per-instance median timing records, and regenerated validation reports accompany this manuscript as supplementary material. No external operational dataset is used. A persistent repository identifier should be added when the author archives the final, reviewed version.

Declarations

This manuscript is a work in progress and is subject to further revisions, refinements, and corrections. Artificial intelligence (AI) tools have been used to assist in its preparation, including aspects of writing, editing, and content development. The author(s) retain full responsibility for the accuracy, originality, and validity of the presented material, including any errors or omissions. The findings, interpretations, and conclusions should be regarded as preliminary and not as definitive results.

Funding and competing interests

Funding information and the competing-interest declaration are to be provided and confirmed by the author before submission.

Space-efficient recovery of an optimal plan

This appendix proves the recovery claim without storing all nn value layers. The construction uses the forward–backward divide-and-conquer principle associated with Hirschberg [2]. The additional argument here is the partition of cumulative-coordinate widths, which prevents an extra logarithmic factor in the time bound.

Forward and backward evaluations

A recovery subproblem specifies boundary times a<ba < b and endpoint grid indices ℓ≤r\ell\le r, meaning Ya=vℓY_a = v_\ell and Yb=vrY_b = v_r. Cumulative purchasing is nondecreasing, so all intermediate coordinates belong to {vℓ,…,vr}\{v_\ell, \ldots, v_r\}. Forward layers use (18) on this restricted grid and initialize cost zero only at vℓv_\ell. Their holding costs are charged at the ending boundary of each transition.

For backward evaluation, let Bt(u)B_t(u) be the minimum cost in periods t+1,…,bt + 1, \ldots, b, conditional on Yt=uY_t = u and Yb=vrY_b = v_r. Initialize Bb(vr)=0B_b(v_r) = 0 and all other values to +∞+\infty. The backward recurrence is

Bt−1(u)=min⁡k{−pt,ku+min⁡v∈V∩[vℓ,vr]v≥u+qt,k, Dt≤v≤U^t(Bt(v)+pt,kv+ht(v−Dt))}.(33)B_{t-1}(u) = \min_k \left\{ -p_{t,k}u + \min_{\substack{v \in V \cap[v_\ell,v_r] \\ v \ge u+q_{t,k},\ D_t \le v \le\widehat{U}_t}} \left(B_t(v) + p_{t,k}v + h_t(v-D_t)\right) \right\}. \tag*{(33)}

It is evaluated only at feasible source coordinates. For a fixed tier, scan uu in decreasing order and maintain the minimum over the expanding suffix v≥u+qt,kv \ge u + q_{t,k}. A backward layer consequently has the same linear-per-tier complexity as a forward layer.

Midpoint selection and recursion

When a<b−1a < b - 1, choose c=⌊(a+b)/2⌋c = \lfloor(a+b)/2 \rfloor. Compute forward costs Ac(v)A_c(v) for periods a+1,…,ca+1,\ldots,c and backward costs Bc(v)B_c(v) for periods c+1,…,bc+1,\ldots,b. Choose a minimizer

vs∈arg⁡min⁡v∈V∩[vℓ,vr]{Ac(v)+Bc(v)}.(34)v_s \in\mathop{\arg\min}_{v \in\mathcal{V} \cap[v_\ell,v_r]} \{A_c(v) + B_c(v)\}. \tag*{(34)}

There is no duplicated holding charge because the backward cost starts strictly after period cc. Release both value arrays, then solve the subproblems (a,c,ℓ,s)(a,c,\ell,s) and (c,b,s,r)(c,b,s,r). When b=a+1b = a+1, set xb=vr−vℓx_b = v_r-v_\ell. When ℓ=r\ell= r, all orders in the subproblem are zero, so no further dynamic program is needed. Initialize the complete output vector to zero once before recursing. Feasibility of a selected subproblem follows from the finite costs in (A.2). At the root, its terminal index is selected by the main forward solve.

Proposition A.1 (Recovery complexity). For a grid of size MM, recovery takes O(nKmax⁡M)O(nK_{\max}M) operations and O(M+n)O(M+n) auxiliary space. For the one-threshold case this is O(nM)O(nM) time.

Proof. Correctness follows by splitting an optimal path at (A.2). Any cheaper child path would improve the parent path, and the concatenation of two minimizing child paths attains the parent’s optimum.

For the running time, define a subproblem’s coordinate width as w=r−ℓw = r-\ell, not its number of grid points. The two child widths sum to ww. Zero-width subproblems require no value-layer computation. For positive width, the number of processed coordinates is w+1≤2ww+1 \le2w. At every recursion depth, the sum of the positive widths is at most the root width, which is at most M−1M-1. A time interval at depth dd has length at most ⌈n/2d⌉\lceil n/2^d \rceil. Thus the value-layer work at that depth is

O(Kmax⁡M⌈n2d⌉)O\left(K_{\max}M\left\lceil\frac{n}{2^d}\right\rceil\right)

Summing over d=0,…,⌈log⁡2n⌉d=0,\ldots,\lceil\log_2 n\rceil gives O(nKmax⁡M)O(nK_{\max}M) because the sum of these ceilings is O(n)O(n). The recursion has O(n)O(n) nodes and writes at most nn purchases.

Only the arrays for the current subproblem need be retained: parent arrays are released before either child is entered. They occupy O(M)O(M) space, the output occupies O(n)O(n), and depth-first recursion uses O(log⁡(n+1))O(\log(n+1)) additional bookkeeping. The original sorted grid is shared by all subproblems.

References

  1. [1]Down, D.G., Karakostas, G., Kolliopoulos, S.G., Rostami, S., 2021. Single-item lot-sizing with quantity discount and bounded inventory. Operations Research Letters 49, 877–882. doi:10.1016/j.orl.2021.11.002.DOI
  2. [2]Hirschberg, D.S., 1975. A linear space algorithm for computing maximal common subsequences. Communications of the ACM 18, 341–343. doi:10.1145/360825.360861.DOI
  3. [3]Koca, E., Yaman, H., Aktürk, M.S., 2014. Lot sizing with piecewise concave production costs. INFORMS Journal on Computing 26, 767–779. doi:10.1287/ijoc.2014.0597.DOI
  4. [4]Love, S.F., 1973. Bounded production and inventory models with piecewise concave costs. Management Science 20, 313–318. doi:10.1287/mnsc.20.3.313.DOI
  5. [5]Ou, J., 2017. Improved exact algorithms to economic lot-sizing with piecewise linear production costs. European Journal of Operational Research 256, 777–784. doi:10.1016/j.ejor.2016.06.040.DOI
  6. [6]Papadopoulos, K., 2026a. Monge matrix searching for lot sizing with piecewise-concave production costs. URL: https://arxiv.org/abs/2610.03277v1. arXiv:2610.03277v1. Preprint; 2 October 2026.
  7. [7]Papadopoulos, K., 2026b. A novel exact algorithm for economic lot-sizing with piecewise linear production costs. Journal of Global Optimization 96, 171–205. doi:10.1007/s10898-026-01636-3.DOI
  8. [8]Papadopoulos, K., 2026c. An O(n log n) algorithm for single-item lot sizing with a one-breakpoint all-units discount and non-increasing prices. URL: https://arxiv.org/abs/2510.11368v4. arXiv:2510.11368v4. Preprint; version revised 5 March 2026.
  9. [9]Shaw, D.X., Wagelmans, A.P.M., 1998. An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs. Management Science 44, 831–838. doi:10.1287/mnsc.44.6.831.DOI
  10. [10]Swoveland, C., 1975. A deterministic multi-period production planning model with piecewise concave production and holding-backorder costs. Management Science 21, 1007–1013. doi:10.1287/mnsc.21.9.1007.DOI
  11. [11]Wagner, H.M., Whitin, T.M., 1958. Dynamic version of the economic lot size model. Management Science 5, 89–96. doi:10.1287/mnsc.5.1.89.DOI

Paper details

vlnc:W_brbbpwb7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Artificial intelligence (AI) tools

View statement
Looking for related papers…
Contents