Metraipolis › archive › dc_bf74bf32e456

Grid Theory and Polynomiality in Dynamic Lot-Sizing — arXiv:2610.03559

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.03559
License (as archived)
CC0-1.0
Archived
2026-10-06T08:25:51.426Z
SHA-256 of the archived text
b82e1e80434c0057b8f35ad0bbcf93b52f7e49272616ed792d6d686a83cfdedb
Stable URL of this page
https://metraipolis.com/documento/dc_bf74bf32e456

How to cite

Grid Theory and Polynomiality in Dynamic Lot-Sizing — arXiv:2610.03559 — arXiv (en), https://arxiv.org/abs/2610.03559 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bf74bf32e456 (Metraipolis archive dc_bf74bf32e456, sha256 b82e1e80434c0057b8f35ad0bbcf93b52f7e49272616ed792d6d686a83cfdedb)
BibTeX
@misc{dcbf74bf32e456,
  title = {Grid Theory and Polynomiality in Dynamic Lot-Sizing — arXiv:2610.03559},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.03559},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bf74bf32e456; sha256 b82e1e80434c0057b8f35ad0bbcf93b52f7e49272616ed792d6d686a83cfdedb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.03559. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Optimization and Control (math.OC) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.03559 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.330Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).