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 arithmetic operations and 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 positive threshold values, the bounds become time and 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 time, where is the total number of price tiers and 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 elements. The apparent quadratic predecessor search in each state then reduces to two prefix minima, giving an 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 bound for their general no-backlogging formulation. Their extensions also use stock-boundary states. In related piecewise-linear models, Ou [5] obtain an algorithm, and Papadopoulos [7] report an algorithm. The latter work was initially circulated as arXiv:2403.16314 and has since appeared in the Journal of Global Optimization. Thus the exponent , 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 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 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 periods. Period has demand , end-of-period inventory bound , and holding cost per unit of ending inventory. All data are finite. An order and inventory satisfy
For the one-threshold model, is common to all periods and . The procurement cost is
Both price sequences are otherwise arbitrary. We minimize
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 applies after period- demand has been met. There is no additional restriction on . A model whose post-order inventory cannot exceed is obtained by setting , provided . Conversely, an end-inventory instance can be represented using post-order bounds . An independent upper bound on is a different constraint and is not included in the main theorem. We treat two terminal policies: prescribed inventory , where , and free inventory . These policies cannot be interchanged. For example, with one period, , , , prices , 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
Then and . Feasibility becomes
Set . Under prescribed terminal inventory, replace by and retain the equality . Under free terminal inventory, no replacement is made. Put
The number of distinct anchors is at most .
Lemma 2.1 (Suffix tightening). Replacing the upper bounds in (5) by preserves the set of complete feasible plans, under either terminal policy.
Proof. For , nonnegative orders imply . Taking the minimum over gives . Conversely, , 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 . The array 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 permits constants depending on a fixed number of distinct positive threshold values. It does not denote fixed-parameter tractability, and is not allowed to grow silently with . 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 ,
An ineligible term has value . The regular-price line may be used above 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 , let be the tightened inventory polytope with additional inequalities
Minimize on the affine objective
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 . An optimal vertex of a best such linear program is an optimum of the original problem.
Proof. For each feasible , identity (7) allows a minimizing tier to be selected independently in every period. Hence the pointwise minimum of the eligible affine objectives equals . There are finitely many tier selections, and every nonempty is compact because . Its affine objective attains a minimum at a vertex. The minimum over all tier selections therefore equals the original optimum. At a minimizing vertex of a best selection, ; feasibility gives the reverse inequality.
Critical cumulative-purchase levels
Define
After duplicate values are removed, let . Then .
Theorem 3.2 (One-threshold critical states). Under either terminal policy, there is an optimal plan with for all .
Proof. Choose the optimal vertex supplied by Lemma 3.1. The possible active equalities are
together with the fixed initial coordinate and any prescribed terminal coordinate. The latter equals and is an anchor.
Consider the path on nodes . Retain the edge 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 , traverse retained edges to any other node in its component. Each edge changes the coordinate by or . Traversing forward adds these increments; traversing backward subtracts them. The path contains at most edges, so the resulting coordinate is with . Feasibility also places it in .
The grid contains exact real quantities determined by the input. Its size does not depend on the numerical magnitude of demand, capacity, or . 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 . Let denote the minimum cost of a path restricted to this grid up to boundary , with . Initialize and all other entries to . For a feasible target , the Bellman equation is
Set outside the feasible band. The first term permits all nonnegative order quantities; the second requires an order of at least . 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 in the prefix . For the second, advance a pointer through the prefix 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 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 arithmetic operations and 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 ; for free terminal inventory, return . Theorem 3.2 shows that this final value equals the unrestricted optimum.
Constructing and sorting (10) takes operations and space. The layers require operations and space. Appendix A proves that a forward–backward midpoint reconstruction takes further operations and space for two tiers. Its additional time and space fit within the displayed bounds. □
A small instance
Consider , zero holding costs, and the data in Table 1, with .
| 1 | 1 | 4 | 5 | 1 | 5 | 4 |
| 2 | 2 | 8 | 10 | 3 | 0 | 2 |
| 3 | 4 | 8 | 5 | 4 | 2 | 0 |
Table 1. An arbitrary-price instance with an optimal cost of 15.
The optimal cumulative coordinates are . Here and the tightened upper bounds are , 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 , let
The cost is for . 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
The one-threshold model is recovered by and , with and .
The eligible-line representation generalizes to
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 , , , and from § 2. Define
Write and . Notice that because is an anchor and every is a grid point. Also, .
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 , minimize the affine objective
on the tightened inventory polytope with additional inequalities . Identity (15) and the argument of Lemma 3.1 give a globally optimal vertex of a best selection.
Retain active edges 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 , so their distance is at most ; the sum is therefore retained in .
The use of and , 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 ,
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 once the grid is sorted.
Algorithm 1 One period of the critical-grid dynamic program
Require: Sorted grid ; previous values ; period
Ensure: Current values
for all
for do
;
for do
while and do
end while
end for
end for
for do
if then
else
end if
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 and target , is equivalent to . Minimizing over eligible tiers gives 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 :
Every offset is nonnegative. Once a partial sum exceeds , it can never contribute to a retained final sum, so clipping is exact. Each stage merges at most 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 . A standard heap-based multiway merge therefore constructs in operations.
For each anchor, the lists of feasible values and of feasible values, with the latter traversed in reverse sum order, are sorted. Merging these lists takes 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
operations. Working space, excluding input storage, is . An optimal plan can be recovered within the same working-space bound using at most additional operations.
Proof. The preceding merges account for preprocessing. The value layers account for operations. The sum and grid arrays, merge heaps, and two value layers occupy space because ; moreover after irrelevant thresholds above are ignored. Processing the original input costs , which is already covered. The reconstruction bounds follow from Appendix A.
Suppose now that every positive threshold belongs to a fixed global set . Periods may use different subsets of this set. Every sum in (16) has the form
Counting the nonnegative integer vectors yields
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 , the problem with arbitrary temporal prices and arbitrary period-specific inventory bounds is solvable in arithmetic operations and working space, including an optimal plan.
Proof. For fixed , , , , and . Substitute these inequalities in Theorem 4.3. The grid-construction term is dominated by .
| Global threshold values | Arithmetic time | Working space |
| One common threshold | ||
| Two distinct values | ||
| Three distinct values | ||
| Fixed values |
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
is guaranteed. Even one positive threshold per period can produce an exponential set: choose and a final feasible cumulative range containing . All subset sums are distinct and survive the truncation. This situation can occur, for example, when a final demand of 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 in every period does not justify treating 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 . Unit prices and holding costs need not be multiples of .
Corollary 5.1 (Existence of a lattice optimum). Under these assumptions, there is an optimal plan whose purchases and inventories are all in .
Proof. Every cumulative-demand value, tightened upper bound, and anchor is a multiple of . 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 be the best cost for end inventory . The initialization is . For every feasible lattice target ,
where at the predecessor set consists only of zero. The condition inside the minimum is precisely the tier eligibility condition for . Every tier again uses an expanding prefix.
Proposition 5.2 (Lattice complexity). With , the optimal value can be computed in operations and working space. Storing one predecessor per state yields an optimal plan with working space.
Proof. Every previous and current inventory layer has at most states. A tier scans both layers once, giving work, and the total tier count is . Corollary 5.1 makes the final lattice optimum exact. Predecessor indices give the stated direct recovery bound.
This is a pseudopolynomial result: can be exponentially large in the binary input length. It is nevertheless useful when stock capacities are moderate in natural units. Choosing a coarser 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- 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 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
Using gives
where has the same threshold and unit prices . Now define
and record the latest index attaining each minimum. The two sequences are non-increasing, with . Replacing by and setting holding costs to zero relaxes the objective while retaining the feasible set. If its optimal purchase cost is , then
Whole-order reconstruction
Let be an optimal relaxed order, and let if and otherwise. Move each whole order to its recorded source:
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 for all . The same statement holds after adding a nonnegative linear holding adjustment to every tier price.
Proof. For positive and , the unit price at quantity is no greater than the unit price at either constituent quantity. Multiplication by and and addition gives the inequality. If one quantity is zero, the claim follows from . 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 , where the expression can be evaluated even before capacity feasibility is checked. Purchases only move backward, so
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 for every , it is globally optimal. The certificate requires one monotone-oracle call and additional operations.
Proof. The reconstruction is feasible by the capacity test, (30), and preservation of terminal inventory. Therefore
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, is also non-increasing. Choosing the latest minimizer yields , 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 before calling a finite-bound oracle.
With finite capacities, acceptance is not guaranteed. For example, take , , , prices and , no holding cost, and zero terminal inventory. The relaxation orders at cost 6. Moving both orders to period 1 produces , whose first ending inventory is . 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 , replace the last relaxed demand by 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 , 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 in (25) still refers to the original periods.
A one-threshold certificate for multi-threshold instances
When positive thresholds exist, let and define
Then : below 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 . Applying (25)–(27) to this surrogate yields another monotone one-threshold relaxation and a lower bound .
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
Whenever (32) holds, proves optimality. With an oracle, this attempted certificate takes operations, including reading and evaluating the tier data.
The extra cost test is essential. With two periods, , , zero holding and terminal inventory, take local thresholds and price pairs . 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.
| Check | One threshold | Multiple/local thresholds |
| Integer-flow cases versus exhaustive inventory DP | 1,000 | 1,000 |
| Rational-lattice cases versus exhaustive inventory DP | 333 | 500 |
| Compatibility with one-threshold implementation | — | 100 |
| Certificate/fallback cases versus exact solver | 333 | 200 |
| Monotone cases with required certificate acceptance | 100 | — |
| Rational cases versus tier-enumeration LPs | 100 | 60 |
| Tier assignments enumerated in those LP tests | 2,036 | 658 |
| Named regression checks | 6 | 6 |
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 ; 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 , , and three replications per combination of horizon, breakpoint count, and capacity regime, giving 54 instances. The common thresholds are the first 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.
| Capacity | range | Grid (s) | Lattice (s) | Ratio | ||
| 1 | Tight | 74–396 | 7 | 0.0505 | 0.0018 | 28.34 |
| 1 | Wide | 70–381 | 31 | 0.0588 | 0.0122 | 4.82 |
| 2 | Tight | 74–375 | 7 | 0.1366 | 0.0020 | 68.73 |
| 2 | Wide | 99–385 | 31 | 0.1548 | 0.0148 | 10.48 |
| 3 | Tight | 68–384 | 7 | 0.1782 | 0.0020 | 90.16 |
| 3 | Wide | 67–386 | 31 | 0.2047 | 0.0172 | 11.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 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 threshold values, the same construction gives time and 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- 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 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 and endpoint grid indices , meaning and . Cumulative purchasing is nondecreasing, so all intermediate coordinates belong to . Forward layers use (18) on this restricted grid and initialize cost zero only at . Their holding costs are charged at the ending boundary of each transition.
For backward evaluation, let be the minimum cost in periods , conditional on and . Initialize and all other values to . The backward recurrence is
It is evaluated only at feasible source coordinates. For a fixed tier, scan in decreasing order and maintain the minimum over the expanding suffix . A backward layer consequently has the same linear-per-tier complexity as a forward layer.
Midpoint selection and recursion
When , choose . Compute forward costs for periods and backward costs for periods . Choose a minimizer
There is no duplicated holding charge because the backward cost starts strictly after period . Release both value arrays, then solve the subproblems and . When , set . When , 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 , recovery takes operations and auxiliary space. For the one-threshold case this is 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 , not its number of grid points. The two child widths sum to . Zero-width subproblems require no value-layer computation. For positive width, the number of processed coordinates is . At every recursion depth, the sum of the positive widths is at most the root width, which is at most . A time interval at depth has length at most . Thus the value-layer work at that depth is
Summing over gives because the sum of these ceilings is . The recursion has nodes and writes at most purchases.
Only the arrays for the current subproblem need be retained: parent arrays are released before either child is entered. They occupy space, the output occupies , and depth-first recursion uses additional bookkeeping. The original sorted grid is shared by all subproblems.
References
- [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]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]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]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]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]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]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]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]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]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]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