An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices

Basic Information

• Paper ID: 2510.11368
• Title: An $O(n\log n)$ Algorithm for Single-Item Capacitated Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
• Author: Kleitos Papadopoulos
• Classification: cs.DS (Data Structures and Algorithms)
• Publication Date: October 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.11368

Abstract

This paper investigates the single-item capacitated lot sizing problem with a one-breakpoint all-units discount under monotonically decreasing prices. The author establishes several novel structural properties of optimal solutions and develops a hybrid dynamic programming approach that maintains a compact representation of the solution space by storing only critical state information and computing intermediate values using linear equations. The algorithm achieves a time complexity of $O(n\log n)$, where $n$ denotes the number of time periods, representing a significant improvement over the previous best $O(n^2)$ algorithm.

Research Background and Motivation

Problem Significance

Lot sizing problems occupy a central position in manufacturing and supply chain management, where enterprises must minimize total costs—including procurement and storage costs—while satisfying demand. Variants of this problem are ubiquitous in practical business applications, particularly when quantity discounts are present.

Limitations of Existing Methods

The related work comparison table provided in the paper reveals that existing algorithms have high time complexity:

• Federgruen and Lee (1990): $O(n^3)$
• Atamtürk and Hochbaum (2001): $O(n^3)$ to $O(n^5)$
• Malekian et al. (2021): $O(n^4)$
• Down et al. (2021): $O(n^2)$ (current best)

Research Motivation

The author employs a "gas station analogy" to intuitively explain the problem: time periods correspond to gas stations, inventory corresponds to fuel in the tank, demand corresponds to distances between stations, and item costs correspond to fuel prices. This analogy facilitates understanding the intuition behind algorithm design.

Core Contributions

1. Established structural properties of optimal solutions: Proved that optimal solutions possess specific mathematical properties under non-decreasing prices and single-breakpoint discounts
2. Proposed a hybrid dynamic programming algorithm: Developed a compact solution space representation method based on segment representation
3. Achieved $O(n\log n)$ time complexity: A significant improvement over the existing best algorithm of $O(n^2)$
4. Designed efficient data structures: Utilized augmented balanced binary search trees to maintain segment information and MV thresholds

Detailed Methodology

Problem Definition

Input:

• $n$ time periods, each period $t$ with demand $d_t$
• Storage capacity $B(t)$ and unit holding cost $h_t$
• Hierarchical pricing function: $p_t(x) = \begin{cases} p_{1,t}x & \text{if } x < Q \\ p_{2,t}x & \text{if } x \geq Q \end{cases}$
• Non-increasing prices: $p_{1,t} \geq p_{1,t+1}$, $p_{2,t} \geq p_{2,t+1}$

Output: Procurement and storage strategy that minimizes total cost

Objective Function: $\min_{x,I} \sum_{t=1}^n (p_t(x_t) + h_t I_t)$

Constraints:

• $I_t = I_{t-1} + x_t - d_t$
• $0 \leq I_t \leq B(t)$
• $I_0 = 0$

Core Algorithm Architecture

1. State Segment Representation

The author introduces the concept of "state segments," where each segment contains:

• Explicit states: $(f, dp(i,f))$, where $f$ is the inventory level and $dp(i,f)$ is the minimum cost to reach that state
• Linear equations: Used to generate implicit states within the segment's coverage range
• Auxiliary information: $p(i,f)$ (price at which $p_2$ fuel was last obtained), $r(i,f)$ (available additional fuel quantity)

2. Key Lemmas

Lemma 1 (2Q Bound): At any station $i$, the optimal solution set $S_b(i)$ containing the first $2Q$ states includes all states necessary to construct the optimal solution set $S_b(i+1)$.

Lemma 2 (Price Monotonicity): For any two states $dp(i,f)$ and $dp(i,w)$ in $S_b(i)$ with $f < w$, we have $p(i,f) \geq p(i,w)$.

Lemma 3 (Continuity): If state $dp(i,f)$ is used to generate an optimal state in $S(i)$, then the generated states form a continuous interval.

3. MV Threshold Mechanism

To efficiently handle dominance relationships between segments, the author designed the MV (Maximum Value) threshold:

Regular MV (boundary checkpoint): $MV(S_1) = \frac{dp(i,g) - dp(i,f)}{g-f}$

Terminal MV (when $S_2$ uses $p_{2,i}$ on the right): $MV_{term}(S_1) = \frac{dp(i,g) + T p_{2,i} - dp(i,f) - a p(i,f)}{L-a}$

Algorithm Flow

Processing at each station includes:

1. Pruning with $p_{1,i}$: Remove dominated adjacent segments
2. Forming $dp(i+1,0)$: Compare costs of direct arrival and refueling arrival
3. Splitting at $d(i,i+1)$: Partition segments into reachable and unreachable categories
4. Batch Updates: Add $Q$ units of $p_{2,i}$ fuel to unreachable segments
5. Linear Merging: Merge batch-updated segments with existing segments in the $[Q,2Q]$ interval
6. Final Pruning: Perform final dominance checks with $p_{1,i}$

Technical Innovations

1. Compactness of Segment Representation

Traditional dynamic programming requires explicit storage of every possible state, whereas the segment representation in this paper only needs to store critical state points and linear equations, significantly reducing space complexity.

2. Efficiency of MV Thresholds

By precomputing MV thresholds and maintaining them in a balanced binary search tree, the algorithm can determine dominance relationships between segments in $O(\log n)$ time.

3. Lazy Update Mechanism

Batch updates and holding cost updates employ lazy labels, avoiding unnecessary computations while maintaining algorithm efficiency.

Experimental Setup

Theoretical Analysis

The paper primarily provides theoretical analysis rather than experimental validation, focusing on proving:

1. Correctness: Through induction, the algorithm produces correct $2Q$-approximate solution sets at each station
2. Time Complexity:
   • At most 2 new segments created per station
   • Total segment count $m_i \leq 2i$
   • Each operation has time complexity $O(\log n)$
   • Total time complexity is $O(n \log n)$

Complexity Analysis

Segment Count Bound (Lemma 7): The optimal $Q$-approximate solution set $S_b(i)$ contains at most $2i$ segments.

Operation Complexity:

• Individual updates: Each removal of dominated segments requires $O(\log n)$
• Batch updates: Lazy label application is $O(1)$
• Splitting/merging: Standard BST operations are $O(\log n)$

Experimental Results

Theoretical Guarantees

The paper provides rigorous theoretical guarantees:

Theorem 1 (Correctness): Under non-increasing unit prices, a single all-units discount threshold, and linear holding costs, Algorithm 1 correctly computes the $2Q$-approximate solution set $S(i)$ and optimal boundary state $dp(i+1,0)$ for each station $i$.

Theorem 2 (Time Complexity): Under segment bounds $m_i \leq 2i$ and augmented balanced tree primitives, the total time complexity for constructing $S(i)$ from $S_b(i)$ is $O(n \log n)$, with space complexity $O(n)$.

Extensibility Analysis

The paper also provides two practical extensions:

1. Handling $B(i) > 2Q$ cases: Addressed through transient in-place expansion for large capacity queries
2. Decision tracking: Mechanism supporting recovery of optimal procurement plans

Related Work

Development Timeline

Research on lot sizing problems dates back decades, with major development directions including:

• Cost function extensions: From linear to piecewise linear and concave functions
• Constraint enrichment: Capacity limits, buyback options, subcontracting, etc.
• Algorithm improvements: Progressive refinement from $O(n^5)$ to $O(n^2)$

Positioning of This Work

Building upon Down et al. (2021)'s $O(n^2)$ algorithm, this paper achieves a breakthrough improvement to $O(n \log n)$ through the introduction of segment representation and MV threshold mechanisms.

Conclusions and Discussion

Main Conclusions

1. Algorithm efficiency: Achieved time complexity improvement from $O(n^2)$ to $O(n \log n)$
2. Theoretical contribution: Established new structural properties of lot sizing problems under monotonic price environments
3. Practical value: The algorithm applies equally to integer and non-integer quantities, with broad applicability

Limitations

1. Price assumptions: Requires non-increasing prices, limiting applicability scope
2. Single-breakpoint restriction: Only handles cases with a single discount threshold
3. Missing experimental validation: The paper primarily provides theoretical analysis without empirical verification on real data

Future Directions

The author proposes research directions including:

1. Investigating broader classes of cost and holding functions that preserve lemma validity
2. Extension to multi-breakpoint discount scenarios
3. Handling non-monotonic price environments

In-Depth Evaluation

Strengths

1. Strong theoretical innovation: Segment representation and MV threshold mechanisms are original contributions
2. Mathematical rigor: Provides complete correctness and complexity proofs
3. High practical value: Significant time complexity improvement has important practical implications
4. Clear exposition: The gas station analogy makes complex problems accessible

Weaknesses

1. Insufficient experimental validation: Lacks practical performance comparisons with existing algorithms
2. Limited applicability scope: Non-increasing price assumptions may not always hold in practice
3. Implementation complexity: Augmented BST implementation is complex and may impact practical application

Impact

1. Academic contribution: Provides new theoretical tools and analytical frameworks for lot sizing problems
2. Practical value: $O(n \log n)$ complexity makes the algorithm suitable for large-scale problems
3. Reproducibility: Paper provides detailed algorithm descriptions and data structure implementations

Applicable Scenarios

The algorithm is particularly suitable for:

1. Large-scale production planning: Long-term planning problems with many time periods
2. Decreasing price environments: Such as technology products and seasonal goods
3. Capacity-constrained inventory management: Supply chain management with limited warehouse capacity

References

The paper cites important works in the lot sizing domain, including:

• Chung and Lin (1988): Early $O(n^2)$ algorithm
• Federgruen and Lee (1990): $O(n^3)$ method introducing all-units discounts
• Atamtürk and Hochbaum (2001): Handling concave cost functions
• Down et al. (2021): Current best $O(n^2)$ algorithm

Overall Assessment: This is a high-quality theoretical computer science paper that achieves significant breakthroughs in lot sizing problems. While lacking experimental validation, its theoretical contributions and algorithmic innovations possess important academic value and practical significance.