Exact algorithms solve lot sizing with discounts and inventory limits

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

Data Structures and Algorithms

Summary

The paper addresses how to efficiently plan purchases of a single product over time when prices include discounts based on the quantity bought, holding costs apply, and inventory storage limits change each period. The authors provide exact algorithms that find the best buying plan, even when prices change unpredictably and discount thresholds vary. Their method uses mathematical tools to optimize purchases while respecting inventory constraints, and it is tested against other techniques to verify accuracy and performance. Different algorithm versions accommodate more complex discount scenarios and inventory rules, balancing time and memory requirements.

What this means in practice

  • For supply chain planners: Plan inventory purchasing schedules that minimize cost when suppliers offer quantity discounts and inventory storage limits vary over time.
  • For inventory management software developers: Implement efficient algorithms to generate optimal buying plans under complex discount and inventory policies for enterprise resource planning systems.$Commercial implications: Enables software products to offer advanced lot sizing features that handle quantity discounts and inventory limits precisely, improving cost savings.

Authors

Kleitos Papadopoulos

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(n^3)$ arithmetic operations and $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 $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $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)$ time, where $P$ is the total number of price tiers and $W$ 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.
View PDFOpen arXiv