Grid Theory and Polynomiality in Dynamic Lot-Sizing
Abstract
Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.
Related
- Dynamic Active Fleet Sizing of Heterogeneous UAV Relays for Post-Disaster Communication Networks
- Adaptive Fractional-Order Fuzzy Sliding Mode Control for Grid-Connected PV Flyback Inverters Under Dynamic Uncertainties
- Behavioral Knowledge Distillation for Dynamic Graph Anomaly Detection in Trustworthy Power Grid Dispatching
- Polynomiality of Stretched Schubert Structure Constants and Key Coefficients
- Polynomiality of the double ramification cycle
BibTeX
@misc{mehiri2026grid,
title = {{Grid Theory and Polynomiality in Dynamic Lot-Sizing}},
author = {El-Mehdi Mehiri and Nabil Absi and Elodie Suzanne},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03559},
eprint = {2610.03559},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03559},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Grid Theory and Polynomiality in Dynamic Lot-Sizing
AU - El-Mehdi Mehiri
AU - Nabil Absi
AU - Elodie Suzanne
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03559
UR - https://arxiv.org/abs/2610.03559
AB - Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.
ER -