PaperlayerView exact revision on arXiv

Source-linked AI summary

Grid Theory and Polynomiality in Dynamic Lot-Sizing

El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne

arXiv:2610.03559v1math.OCcs.DMcs.DSmath.CO

TL;DR

Dynamic lot-sizing research asks how production and inventory structure relates to computational complexity, including when boundary-generated cumulative-production states admit a polynomial representation. Grid Theory characterizes an optimal trajectory using additive grids and separates that structural result from the question of grid size. Its results show that optimal production can be restricted to boundary-based discrete states, but those grids may still be exponential.

  • Problem

    Although boundary structure generates candidate cumulative-production levels, it remains unclear when those levels admit a polynomial representation.

    Source: §1 · p. 2

  • Method

    Grid Theory uses extreme-point boundary structure to construct additive grids containing an optimal cumulative-production trajectory and studies the size of that state space.

    Source: §1 · pp. 2–3

  • Results

    Within each regeneration interval, an optimal extreme solution has all but at most one production quantity on a boundary, and its cumulative trajectory can be restricted to additive grids.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    An optimality theorem that identifies a discrete state space is not by itself a polynomiality result; the grid must also admit a compact representation.

    Source: §1 · p. 3, §3.5 · p. 10

    Additive grids may contain exponentially many points, so the Main Grid Theorem alone does not establish polynomial solvability.

    Source: §1 · p. 3, §3.5 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The section asks when production boundaries generate a polynomially representable cumulative-production state space. Grid Theory separates the question of which states contain an optimal trajectory from whether those states can be compactly represented.

1 Introduction

  • An optimal trajectory lying on an additive grid does not by itself imply polynomial solvability, because the grid may contain exponentially many points.Distinct powers-of-two capacities, for example, generate exponentially many subset sums.Source: §1 · p. 3
  • Bounded additive dimension yields a polynomially constructible grid envelope and a polynomial-time grid-based dynamic program.Additive dimension measures how many aggregate coordinates describe the resource quantities generating the grid.Source: §1 · p. 3
  • The framework covers constant, finite-level, polynomial, periodic, and piecewise-polynomial capacities, as well as minimum order quantities.Fixed-degree polynomial and piecewise-polynomial capacities can have a number of distinct values that grows with the planning horizon while still generating polynomial additive grids.Source: §1 · pp. 3–4
  • Grid Theory is a framework for identifying when optimal-solution geometry yields a discrete cumulative state space and when its additive complexity is small enough for polynomial solvability.The dynamic program is essentially immediate once a polynomial additive grid has been identified.Source: §1 · p. 3
  • Within every regeneration interval, all but at most one production quantity can be chosen at a production bound.The model allows arbitrary period-dependent lower and upper production bounds.Source: §1 · p. 3
  • The Main Grid Theorem places an entire optimal cumulative-production trajectory on additive grids generated from production boundaries.The grids can be constructed forward from earlier cumulative demand levels and backward from future cumulative demand levels, without using the possibly interior quantity as a generator.Source: §1 · pp. 2–3
  • Once the grid is sorted, the dynamic program runs in time linear in grid cardinality per period.The paper also gives an equivalent layered shortest-path model.Source: §1 · p. 3

2 Structural Foundations

The model allows positive production between period-specific lower and upper bounds, encompassing capacitated lot-sizing and minimum-order-quantity variants. Its extreme-point structure limits interior production to at most one period per regeneration interval.

2.1 A boundary-constrained dynamic lot-sizing model

  • Activated production lies between nonnegative bounds Lt and Ut (0 ≤ Lt ≤ Ut); setting Lt=0, Ut=Ct gives classical single-item capacitated lot-sizing with time-dependent capacity Ct, while Lt>0 introduces a minimum order quantity.Source: §2.1 · pp. 4–5

2.2 Cumulative production formulation

  • With setup decisions fixed, production and inventory decisions can be described through the cumulative production trajectory, whose required state values motivate the paper's structural analysis.The cumulative formulation follows by summing inventory balance equations and rewriting production-bound constraints.Source: §2.2 · p. 5

2.3 Regeneration intervals

  • A regeneration interval runs between consecutive zero-inventory periods, fixing its total production while allowing feasible redistribution among its periods.Intermediate inventories are strictly positive; the endpoints have cumulative production equal to cumulative demand.Source: §2.3 · p. 5

2.4 Extreme point structure

  • At most one production quantity per regeneration interval need be partially utilized; all remaining quantities can lie in the boundary sets {0, Lt, Ut}.This boundary structure holds for extreme points of the fixed-setup production polytope.Source: §2.4 · p. 6
  • The boundary property requires no regularity in the lower- or upper-bound sequences, including monotonicity, stationarity, or a fixed number of levels.Those profile assumptions matter later when determining whether the additive state sets have polynomial cardinality.Source: §2.4 · p. 6

3 Grid Theory

Grid Theory uses production boundaries and cumulative-demand anchors to construct discrete sets containing an optimal cumulative production trajectory. The Main Grid Theorem establishes this optimality property, while the paper distinguishes it from the separate question of whether the grids are compact enough for polynomial-time computation.

3.1 Boundary sums and additive grids

  • Boundary sum sets collect sums formed by independently choosing 0, Lu, or Uu for each period in an interval.Cumulative demand levels serve as anchors from which candidate cumulative production levels are generated.Source: §3.1 · p. 7

3.2 Positive and negative grids

  • Positive grids represent cumulative production from earlier demand anchors by adding boundaries, while negative grids represent it from future anchors by subtracting boundaries.Period-dependent grids retain whether the contributing boundaries come from preceding or following periods.Source: §3.2 · pp. 7–8

3.3 The Main Grid Theorem

  • The Main Grid Theorem guarantees an optimal solution whose complete cumulative production trajectory lies in the period-specific additive grids.The grids are built from cumulative-demand anchors and sums or differences of production boundaries.Source: §3.3 · pp. 8–9

3.4 Interpretation: optimality versus state-space compression

  • The Main Grid Theorem identifies an optimality-preserving state space, but does not establish that the state space is small or compactly representable.Grid Theory treats state sufficiency and state-space compression as separate questions.Source: §3.4 · p. 9
  • The possible partially utilized period need not generate a grid value: the representation switches direction around it, using both positive and negative grids.This follows because all other production quantities in the regeneration interval lie on their boundary sets.Source: §3.4 · p. 10

3.5 The additive grid can be exponential

  • With C1,...,C_{T−1} distinct powers of two, every subset gives a different sum, so |G_{T−1}| ≥ 2^{T−1}; under demand only in the final period equal to total capacity, the additive grid may be exponential.Source: §3.5 · p. 10

4 Grid Dynamic Programming

Grid Dynamic Programming searches cumulative-production states in the additive grids, with transitions representing feasible production quantities and their costs. The recurrence is optimal by the Main Grid Theorem, and a monotone-deque implementation accelerates computation once the grids are given and sorted.

4.1 State space

  • The state space consists of period-grid pairs, and a transition from r to s represents production xt = s − r, feasible when it is zero or between Lt and Ut.The objective adds setup and production costs to holding cost on inventory s − Dt.Source: §4 · p. 11, §4.1 · p. 11, §4.2 · p. 11

4.2 Dynamic programming recurrence

  • The GDP recurrence returns the optimal value because the Main Grid Theorem guarantees that restricting cumulative production to the additive grids loses no optimality.A state records the period and cumulative production; transitions correspond to feasible zero or positive production.Source: §4.2 · pp. 11–12, §4 · p. 11, §4.1 · p. 11

4.3 Shortest path interpretation

  • The GDP formulation is equivalent to a shortest-path problem in a layered acyclic graph whose paths encode grid-restricted production plans and their objective costs.The initial and terminal nodes are (0, 0) and (T, DT).Source: §4.3 · p. 12

4.4 Complexity

  • A monotone deque maintains predecessor minima over moving feasible-production windows, reducing the transition scan to time linear in the number of grid states, given sorted period grids.Each predecessor enters and leaves the deque at most once.Source: §4.4 · p. 13

O (NG log NG + TNG)

  • The common-grid implementation runs in O(NG log NG + TNG) time and uses O(NG) working memory for the optimal value.Here NG is the size of the common grid; the time bound includes sorting it once.Source: O (NG log NG + TNG) · p. 14, §4.4 · p. 14

4.4 Complexity

  • The GDP complexity depends on the number of additive grid points represented, which may still be exponential despite containing an optimal trajectory.The later polynomiality analysis therefore asks when boundary structure generates a polynomial-size grid.Source: O (NG log NG + TNG) · p. 14

5 Polynomial Grid Theory

This section explains how polynomial-size grid envelopes and bounded additive dimension provide a structural route to polynomial-time solvability, extending the cumulative-grid result to separable concave production and inventory costs. For such costs, bounded additive dimension yields exact polynomial-time solvability by GDP when costs are exactly evaluable in polynomial time; linear costs are needed only for accelerated implementation.

5.1 The polynomial grid condition

  • A polynomial-time constructible envelope of polynomial size containing the exact grid points suffices for GDP to preserve optimality and run in polynomial time.The envelope may include unrealizable cumulative production levels; feasibility is still enforced by the dynamic-programming transitions.Source: §5.1 · pp. 14–15

5.2 Additive dimension

  • Additive dimension compresses exponentially many boundary selections into a fixed-dimensional integer vector with polynomially bounded coordinate ranges.It need not bound the number of distinct boundary values: fixed-degree polynomial capacities can have T distinct values while their sums use power-sum coordinates.Source: §5.2 · pp. 16–17

5.3 The General Polynomiality Theorem

  • Bounded additive dimension guarantees a polynomial grid condition and exact polynomial-time solvability by the GDP algorithm.This is a sufficient condition, not a characterization: families without bounded additive dimension may still be polynomially solvable by other means.Source: §5.3 · pp. 17–18

5.4 Extension to separable concave costs

  • For separable concave production and inventory costs, an optimal solution still has at most one interior production quantity per regeneration interval, preserving the same cumulative grid.The monotone deque acceleration does not generally apply to the extended cost recurrence.Source: §5.4 · p. 19
  • Families of Pconc instances with bounded additive dimension are exactly solvable in polynomial time by GDP when their concave costs are exactly polynomial-time evaluable.Source: §5.4 · p. 19
  • The MGT preserves an optimal solution on the linear-cost additive grid, whose polynomial-size envelope supports a polynomial number of GDP transitions with polynomial-time costs.The recurrence examines at most |bG|^2 predecessor–successor pairs per period.Source: §5.4 · p. 20
  • The direct concave-cost dynamic program has a generic bound O(T^(3+2κ)), while linear costs are needed only for the accelerated O(T|bG|) implementation.Grid generation, sorting, and exact cost evaluation add polynomial overhead.Source: §5.4 · p. 20

6 Polynomial Families

Grid Theory uses low-dimensional additive representations of production boundaries to construct polynomial grid envelopes, then applies the General Polynomiality Theorem. The section illustrates this approach for uncapacitated lot-sizing and constant capacity.

6 Polynomial Families

  • For each family, identifying additive coordinates allows a polynomial grid envelope and application of the General Polynomiality Theorem.The framework can use simpler exact or enclosing boundary-sum sets when available.Source: §6 · p. 20

6.1 Uncapacitated baseline

  • O(T^2) time and O(T) working memory solve uncapacitated linear-cost lot-sizing through a grid of cumulative demand anchors.The result recovers the classical quadratic order of the Wagner–Whitin dynamic program.Source: §6.1 · p. 20

6.2 Constant capacity

  • O(T^3) time and O(T^2) working memory solve the constant-capacity problem using a grid arising from a one-dimensional additive representation.The boundary sums are multiples of the constant capacity.Source: §6.2 · pp. 20–21

6.3 Constant minimum order quantity

The section applies Grid Theory to lower production boundaries and to simultaneous constant minimum-order and capacity bounds. The number of independent boundary resources determines the grid dimension and the resulting algorithmic bounds.

6.3 Constant minimum order quantity

  • O(T^3) time and O(T^2) working memory solve uncapacitated lot-sizing with a constant minimum order quantity.The constant lower production boundary generates an O(T^2) cumulative production grid under the paper’s linear cost structure.Source: §6.3 · pp. 21–22

6.4 Constant capacity and constant minimum order quantity

  • O(T^4) time and O(T^3) working memory solve the constant-capacity, constant-minimum-order-quantity problem using two additive coordinates.The two resources generate a two-dimensional family of boundary sums.Source: §6.4 · p. 22
  • One constant boundary resource yields an essentially one-dimensional family of boundary sums, while two independent constant resources yield a two-dimensional family.The simultaneous-bound case has a two-dimensional additive representation with basis values L and C.Source: §6.4 · p. 22

6.5 A fixed number of capacity levels

A fixed number of capacity levels gives a fixed-dimensional additive representation, regardless of the order in which those levels occur. The resulting grid yields a polynomial-time algorithm.

6.5 A fixed number of capacity levels

  • Counting how many periods use each capacity level represents every capacity subset sum with R coordinates.The boundary resource profile therefore has additive dimension at most R.Source: §6.5 · p. 23
  • For fixed R capacity levels, the GDP algorithm solves the capacitated lot-sizing problem in O(T^(R+2)) time.The common cumulative production grid has O(T^(R+1)) states.Source: §6.5 · p. 23
  • The result is independent of capacity-level order, so profiles may switch arbitrarily among the fixed set of values.The same result applies to a fixed number of shifts, production modes, exogenous operating states, or recurring capacity levels.Source: §6.5 · p. 23

6.6 Fixed-degree polynomial capacities

For fixed-degree polynomial capacities, the boundary sums admit a low-dimensional additive representation, which supports polynomial solvability through the GDP algorithm.

6.6 Fixed-degree polynomial capacities

  • For fixed degree d, polynomial capacities have additive dimension at most d + 1, with polynomial-time-computable coordinates of polynomially bounded encoding length.The capacity coefficients must ensure C_t ≥ 0 over the planning horizon.Source: §6.6 · pp. 23–24
  • For every fixed degree d, the capacitated lot-sizing problem with the stated polynomial capacity profile is solvable by the GDP algorithm.The corollary’s running-time expression is incomplete in the supplied passage.Source: §6.6 · p. 24
  • An affine capacity profile C_t = γ0 + γ1t has additive dimension at most two, with subset sums determined by two coordinates.The passage names the coordinates as |S| and a second, truncated expression.Source: §6.6 · p. 24

6.7 Seasonal and periodic capacities

Fixed-period seasonal capacities and piecewise fixed-degree polynomial capacities are polynomially solvable by the GDP algorithm. Their additive representations depend on the fixed cycle or on the fixed number of pieces and degree.

6.7 Seasonal and periodic capacities

  • For every fixed period q, periodic capacities are solvable in polynomial time by the GDP algorithm.The cycle may contain up to q distinct capacity values; when it contains R distinct values, the common grid has cardinality O(T^(R+1)) and running time is O(T^(R+2)).Source: §6.7 · p. 24

6.8 Piecewise polynomial capacities

  • Piecewise polynomial capacity profiles have additive dimension at most R(d + 1) when the number of pieces R and maximum degree d are fixed.Their additive coordinates are polynomial-time computable and have polynomially bounded encoding length.Source: §6.8 · p. 24
  • If both the number of pieces and maximum polynomial degree are fixed independently of T, the capacitated lot-sizing problem is solvable by the GDP algorithm.The family includes successive production phases, seasonal regimes, planned expansions, temporary reductions, and polynomial deterioration patterns.Source: §6.8 · p. 25

6.9 Relation to previous complexity results

The comparison with prior complexity results distinguishes Grid Theory’s structural explanation of polynomiality from specialized algorithms and other routes to tractability.

6.9 Relation to previous complexity results

  • The literature includes polynomial families for which a common structural argument can be distinguished from improving a specialized algorithm for a particular model.Table 1 summarizes representative complexity results and their relation to Grid Theory.Source: §6.9 · p. 26
  • The polynomial grid condition is sufficient, not necessary, because cost-induced dominance can yield polynomiality without a polynomial-cardinality additive capacity grid.The Chung–Lin family illustrates this distinction.Source: §6.9 · p. 26
  • The Chung–Lin family shows that polynomiality may come from cost-induced dominance even when the additive capacity grid is not guaranteed to have polynomial cardinality.This distinguishes a structural explanation from a claim that every polynomial family must satisfy the grid condition.Source: §6.9 · p. 26

7 Discussion

The discussion frames Grid Theory around exogenous production boundaries, regeneration anchors, extreme-solution boundaries, and additive compression. It also clarifies the framework’s limits and identifies possible extensions as directions for further theory.

7 Discussion

  • Grid Theory’s mechanism combines regeneration anchors, boundary structure in extreme solutions, and additive compression of the boundary values generating cumulative production states.Source: §7 · p. 26

7.1 What the framework explains

  • Polynomiality depends on the complexity of additive combinations, not merely on the number of periods or distinct boundary values.Bounded additive dimension is more flexible than requiring a fixed finite set of capacity levels.Source: §7.1 · p. 26
  • The Main Grid Theorem preserves optimality through discretization, whereas the General Polynomiality Theorem compresses the grid; an exponential-grid example motivates separating them.Source: §7.1 · p. 26

7.2 What the framework does not imply

  • Bounded additive dimension is sufficient, not necessary, for polynomial solvability; an exponential additive grid neither proves NP-hardness nor makes explicit enumeration polynomial.Source: §7.2 · p. 26
  • The results mainly assume exogenous boundaries; with dynamic capacity adjustment, tractability also depends on the state-transition system generating those boundaries.Source: §7.2 · p. 26
  • Additional resources that introduce state variables or coupling constraints require a new structural theorem, including a Main Grid Theorem for the enlarged state space.Source: §7.2 · p. 26

7.3 Directions suggested by the framework

  • Proposed extensions include multidimensional grids, endogenous boundaries, and compression beyond additive dimension; these remain directions for further theory.The paper’s stated result is narrower: for exogenous production boundaries, additive structure can make the cumulative state space induced by the Main Grid Theorem polynomially representable.Source: §7.3 · p. 27

8 Conclusion

Grid Theory connects optimal production-bound structure to discrete cumulative-production grids, then distinguishes grid existence from the compressibility needed for polynomial solvability. It covers several established and growing-capacity families, while remaining a sufficient mechanism rather than a necessary characterization.

8 Conclusion

  • An optimal trajectory can be restricted to forward and backward additive grids generated from cumulative-demand anchors and production-boundary values.This follows from the result that each regeneration interval contains at most one partially utilized production period.Source: §8 · p. 27
  • Bounded-dimensional, polynomially accessible additive representations yield a polynomial-size grid envelope and an exact polynomial-time grid-based dynamic programming algorithm.The exact additive grid may be exponentially large, so grid existence alone does not establish polynomiality.Source: §8 · pp. 27–28
  • The framework covers constant capacities, constant minimum order quantities, fixed numbers of capacity levels, and polynomial or piecewise-polynomial capacity profiles.Polynomiality can hold even when the number of distinct capacity values grows with the horizon.Source: §8 · p. 27
  • Grid Theory offers a reusable sufficient mechanism, not a necessary characterization of polynomial lot-sizing or a replacement for stronger specialized algorithms.Source: §8 · p. 27
Loading 2610.03559v1…