betaFeedback

WorksComputer Science

An O(nlog⁡n)O(n\log n) Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold Q>0Q > 0 for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of QQ. We give an exact O(nlog⁡n)O(n\log n)-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using O(n)O(n) working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in O(nlog⁡n)O(n\log n) time and O(nlog⁡n)O(n\log n) space.

Introduction

Single-item dynamic lot sizing is a fundamental problem in inventory and production planning: given deterministic demands d1,…,dnd_1,\ldots,d_n over a finite planning horizon of nn periods, one chooses nonnegative order quantities q1,…,qnq_1,\ldots,q_n to satisfy demand without backlogging while minimizing total procurement and inventory holding costs. Under an all-units quantity discount with threshold Q>0Q > 0, ordering 0≤qi<Q0 \le q_i < Q units in period ii incurs a regular unit price p1,ip_{1,i}, whereas ordering qi≥Qq_i \ge Q units lowers the unit price on the entire batch to p2,i≤p1,ip_{2,i} \le p_{1,i}. Because the procurement cost function drops discontinuously at qi=Qq_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 {p1,i}\{p_{1,i}\} and {p2,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(nlog⁡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 2Q2Q. 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≤p2,i≤p1,i0 \le p_{2,i} \le p_{1,i} and nonnegative linear holding costs hi≥0h_i \ge0, for both continuous (G=R≥0\mathcal{G} = \mathbb{R}_{\ge0}) and integral (G=Z≥0\mathcal{G} = \mathbb{Z}_{\ge0}) quantity domains. The formal model and arithmetic conventions are stated in § 2.

Theorem 1.1 (Optimal values in O(nlog⁡n)O(n \log n) time and linear space). For any nn-period uncapacitated instance satisfying (2.1)–(2.3), the minimum total cost OPT\mathrm{OPT} with free terminal inventory, together with the zero-terminal prefix optimum OPTk,0\mathrm{OPT}_{k,0} for every k∈{1,…,n}k \in\{1,\ldots,n\}, can be computed online in O(nlog⁡n)O(n \log n) time and O(n)O(n) working space. These bounds hold for both G=R≥0\mathcal{G} = \mathbb{R}_{\ge0} and G=Z≥0\mathcal{G} = \mathbb{Z}_{\ge0} 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 (q1,…,qn)∈Gn(q_1,\ldots,q_n) \in\mathcal{G}^n for the free-terminal problem—or for any prescribed zero-terminal prefix 1,…,k1,\ldots,k—can be computed in O(nlog⁡n)O(n \log n) time and O(nlog⁡n)O(n \log n) space.

The proof is organized around three main steps that decouple speculative physical stockpiling from compressed frontier maintenance:

  1. Online effective-price reduction and retroactive aggregation (Section 2.2). At each period ii, we maintain in O(1)O(1) time the cheapest holding-cost-adjusted historical regular price αi\alpha_i and discounted price βi\beta_i, together with their attaining origin periods s(i),r(i)≤is(i), r(i) \le i. Replacing (p1,i,p2,i)(p_{1,i},p_{2,i}) by (αi,βi)(\alpha_i,\beta_i) defines a virtual lot-sizing problem whose prices are no longer arbitrary: they satisfy the non-speculative inequalities αi+1≤αi+hi\alpha_{i+1} \le\alpha_i + h_i and βi+1≤βi+hi\beta_{i+1} \le\beta_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)) and aggregating colliding orders never worsens price tiers: combining regular orders that cross QQ only unlocks a cheaper discounted rate p2,t≤p1,tp_{2,t} \le p_{1,t}, while discounted virtual orders already have size at least QQ.

  1. Simultaneous normal form under non-speculative prices (Sections 2.3–2.4). Unlike monotone prices (βi+1≤βi\beta_{i+1} \le\beta_i), non-speculative effective prices permit αi+1>αi\alpha_{i+1} > \alpha_i and βi+1>βi\beta_{i+1} > \beta_i when hi>0h_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=1mI^t\Phi(\hat{I}) = \sum_{t=1}^{m} \hat{I}_t yields one optimal virtual schedule that simultaneously satisfies q^i>0⟹I^i−1<di\hat{q}_i > 0 \Longrightarrow\hat{I}_{i-1} < d_i, I^i−1<2Q\hat{I}_{i-1} < 2Q, and I^n<Q\hat{I}_n < Q. This justifies an auxiliary dynamic program supported on [0,2Q][0,2Q] that overestimates certain positive-inventory states without altering OPT\mathrm{OPT} or any OPTk,0\mathrm{OPT}_{k,0}. Subtracting βiy\beta_i y makes the regular departure envelope nondecreasing above QQ 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 that translates uniformly by +hi+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) 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). Two-stage recovery combines path-copying persistence on the auxiliary frontier with O(n)O(n) origin aggregation.

Relation to prior work

Dynamic lot sizing originates with Wagner and Whitin [13], who gave an O(n2)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(nlog⁡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>0Q > 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(n2)O(n^2) algorithm for incremental discounts and an O(n3)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(n4)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 mm stationary breakpoints, Koca, Yaman, and Aktürk [7] established polynomial solvability in O(n2m+3)O(n^{2m+3}) time (O(n5)O(n^5) for m=1m = 1). Ou [9] improved the piecewise-linear bound to O(nm+2log⁡n)O(n^{m+2}\log n) (O(n3log⁡n)O(n^3\log n) for m=1m = 1) using range-minimum queries, and Papadopoulos [10] removed the logarithmic factor to obtain O(nm+2)O(n^{m+2}) (O(n3)O(n^3) for m=1m = 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(nlog⁡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(nlog⁡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≥1n \ge1 periods indexed by i=1,…,ni = 1,\ldots,n. Let G=R≥0\mathcal{G} = \mathbb{R}_{\ge0} in the continuous model and G=Z≥0\mathcal{G} = \mathbb{Z}_{\ge0} in the integral model. In period ii, deterministic demand is di∈Gd_i \in\mathcal{G}, the holding cost per unit of inventory remaining after demand is hi≥0h_i \ge0, and the common all-units discount threshold is Q∈GQ \in\mathcal{G} with Q>0Q > 0. The regular unit price p1,ip_{1,i} and discounted unit price p2,ip_{2,i} are arbitrary finite real numbers satisfying only the within-period discount ordering

0≤p2,i≤p1,i<+∞,i=1,…,n.(1)0 \le p_{2,i} \le p_{1,i} < +\infty,\qquad i = 1,\ldots,n. \tag*{(1)}
ReferenceProcurement cost structureCapacity and pricesComplexity
Wagelmans et al. [12], Aggarwal & Park [1]Fixed setup plus linearUncapacitated, arbitrary pricesO(nlog⁡n)O(n \log n)
Federgruen & Lee [6]Setup plus 1-breakpoint all-units discountUncapacitated, non-increasing pricesO(n3)O(n^3)
Koca et al. [7]Piecewise concave (mm stationary breakpoints)Uncapacitated, arbitrary pricesO(n2m+3)O(n^{2m+3})
Ou [9]Piecewise linear (mm stationary breakpoints)Uncapacitated, arbitrary pricesO(nm+2log⁡n)O(n^{m+2} \log n)
Malekian et al. [8]Setup plus 1-breakpoint all-units discountConstant capacity, non-increasing pricesO(n4)O(n^4)
Papadopoulos [10]Piecewise linear (mm stationary breakpoints)Uncapacitated, arbitrary pricesO(nm+2)O(n^{m+2})
Papadopoulos [11]Linear with 1-breakpoint all-units discountTime-varying capacity, non-increasing pricesO(nlog⁡n)O(n \log n)
This paperLinear with 1-breakpoint all-units discountUncapacitated, arbitrary pricesO(nlog⁡n)O(n \log n)

Table 1. Comparison of exact time complexities for related single-item lot-sizing models over nn periods.

No temporal monotonicity is assumed across periods. The procurement cost of ordering q∈Gq \in\mathcal{G} units in period ii is

Pi(q)={p1,iq,0≤q<Q,p2,iq,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)}

Note that Pi(0)=0P_i(0)=0 and PiP_i is subadditive: Pi(q+r)≤Pi(q)+Pi(r)P_i(q+r) \le P_i(q)+P_i(r) for all q,r≥0q,r \ge0, because q+r<Qq+r<Q keeps both summands in the regular tier whereas q+r≥Qq+r \ge Q prices the combined batch at p2,i≤p1,ip_{2,i} \le p_{1,i}.

For any prefix horizon k∈{1,…,n}k \in\{1,\ldots,n\}, an order sequence q=(q1,…,qk)∈Gkq=(q_1,\ldots,q_k) \in\mathcal{G}^k and its induced inventory sequence I=(I0,I1,…,Ik)∈Gk+1I=(I_0,I_1,\ldots,I_k) \in\mathcal{G}^{k+1} are feasible if

I0=0,Ii=Ii−1+qi−di≥0,qi≥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)}

There is no upper capacity on IiI_i or qiq_i, and no disposal or resale operation. The total cost on prefix 1,…,k1,\ldots,k is

References

  1. [1]A. Aggarwal and J. K. Park. Improved algorithms for economic lot size problems. Operations Research, 41(3):549–571, 1993.DOI
  2. [2]A. Atamtürk and D. S. Hochbaum. Capacity acquisition, subcontracting, and lot sizing. Management Science, 47(8):1081–1100, 2001.DOI
  3. [3]G. E. Blelloch, D. Ferizovic, and Y. Sun. Just join for parallel ordered sets. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’16), pages 253–264. ACM, 2016.DOI
  4. [4]P. Brass. Advanced Data Structures. Cambridge University Press, 2008.DOI
  5. [5]C.-S. Chung and C.-H. M. Lin. An O(T²) algorithm for the NI/G/NI/ND capacitated lot size problem. Management Science, 34(3):420–426, 1988.DOI
  6. [6]A. Federgruen and C.-Y. Lee. The dynamic lot size model with quantity discount. Naval Research Logistics, 37(5):707–713, 1990.
  7. [7]E. Koca, H. Yaman, and M. S. Aktürk. Lot sizing with piecewise concave production costs. INFORMS Journal on Computing, 26(4):767–779, 2014.DOI
  8. [8]Y. Malekian, S. H. Mirmohammadi, and M. Bijari. Polynomial-time algorithms to solve the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount. Computers & Operations Research, 134:105373, 2021.DOI
  9. [9]J. Ou. Improved exact algorithms to economic lot-sizing with piecewise linear production costs. European Journal of Operational Research, 256(3):777–784, 2017.DOI
  10. [10]K. Papadopoulos. A novel exact algorithm for economic lot-sizing with piecewise linear production costs. Journal of Global Optimization, 2026.
  11. [11]K. Papadopoulos. An O(n log n) algorithm for single-item lot sizing with a one-breakpoint all-units discount and non-increasing prices. Preprint, https://arxiv.org/abs/2510.11368v4, 2026.
  12. [12]A. Wagelmans, S. van Hoesel, and A. Kolen. Economic lot sizing: An O(n log n) algorithm that runs in linear time in the Wagner–Whitin case. Operations Research, 40(S1):S145–S156, 1992.DOI
  13. [13]H. M. Wagner and T. M. Whitin. Dynamic version of the economic lot size model. Management Science, 5(1):89–96, 1958.

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents