pith. sign in

arxiv: 1907.02405 · v1 · pith:HP2SGAIOnew · submitted 2019-07-04 · 🧮 math.OC · cs.AI

A global constraint for the capacitated single-item lot-sizing problem

Grigori German , Hadrien Cambazard , Jean-Philippe Gayon , Bernard Penz This is my paper

Pith reviewed 2026-05-25 09:12 UTC · model grok-4.3

classification 🧮 math.OC cs.AI
keywords lot-sizingglobal constraintbound consistencyconstraint programmingdynamic programmingmixed integer linear programmingcapacitated production
0
0 comments X

The pith

The capacitated single-item lot-sizing problem can be formulated as a global constraint that achieves bound consistency in pseudo-polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper sets up a constraint programming framework for the single-item lot-sizing problem that includes time-varying lower and upper bounds on production and inventory plus time-varying holding, production, and setup costs. The authors introduce a global constraint built around a time decomposition that yields a new lower bound. They prove that bound consistency for this NP-hard problem can be enforced in pseudo-polynomial time and in polynomial time when costs are omitted. Experiments compare the global constraint against mixed-integer linear programming and a decomposed constraint programming model, showing that the global constraint finds solutions the decomposed model misses and that constraint programming remains competitive once combinatorial side constraints are added.

Core claim

The capacitated single-item lot-sizing problem with time-varying bounds and costs is formulated as a global constraint. Bound consistency for this constraint is achieved in pseudo-polynomial time by means of a time decomposition that supplies a valid lower bound; without costs the same result holds in polynomial time. Filtering rules derived from dynamic programming algorithms exploit the decomposition on hard instances.

What carries the argument

A global constraint for the lot-sizing problem that uses time decomposition to compute lower bounds supporting bound-consistency filtering.

Load-bearing premise

The time decomposition yields a valid lower bound that supports correct bound-consistency filtering without introducing spurious domain reductions when costs and capacity constraints interact.

What would settle it

An instance in which the filtering rules derived from the time decomposition remove a feasible production plan from the domain.

Figures

Figures reproduced from arXiv: 1907.02405 by Bernard Penz, Grigori German, Hadrien Cambazard, Jean-Philippe Gayon.

Figure 1
Figure 1. Figure 1: Flow representation of the single-item lot-sizing problem [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The linear relaxation of MILP_AGG is a minimum cost network flow problem [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Sub-problem (Lu,v) Sub-problem (L1T ) corresponds to the entire problem (L). As there is no demand after period v and no lower bounds of production, any solution of (Lu,v) is dominated by a solution with null inventory at the end of period v (Iv = 0). Note also that, in (Lu,v), some demands in {du, du+1, . . . , dv} can be satisfied by a production made without setup cost before period u. Finally, an optim… view at source ↗
Figure 4
Figure 4. Figure 4: The constraint network (Lr) and the corresponding intersection graph Theorem 4. BC and RC are equivalent for (F). Proof. By definition, RC implies BC for (F). Conversely, assume BC for (F). In order to show the converse, we show that if k ∈ Jlij , uij K, then k belongs to a bound support for (F). Let i0 be a direct predecessor of j0 in the graph. BC implies that there exists x 0 (resp. x 00) an integer sol… view at source ↗
Figure 5
Figure 5. Figure 5: represents the different lower bounds computed while filtering the value it for the variable It. It belongs to the sub-problem (Lu,v), lbBefore(u−1) and lbAf ter(v + 1) are computed via DPWisp outside that sub-problem. 1 … 𝑢 − 1 𝒖 … 𝑡 … 𝒗 𝑣 + 1 … 𝑇 𝐼𝑡 = 𝑖𝑡 𝑡 + 1 𝑙𝑏𝐵𝑒𝑓𝑜𝑟𝑒(𝑢 − 1) 𝑓(𝑡, 𝑖𝑡) 𝑓𝑟(𝑡, 𝑖𝑡) 𝑙𝑏𝐴𝑓𝑡𝑒𝑟(𝑣 + 1) [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
read the original abstract

The goal of this paper is to set a constraint programming framework to solve lot-sizing problems. More specifically, we consider a single-item lot-sizing problem with time-varying lower and upper bounds for production and inventory. The cost structure includes time-varying holding costs, unitary production costs and setup costs. We establish a new lower bound for this problem by using a subtle time decomposition. We formulate this NP-hard problem as a global constraint and show that bound consistency can be achieved in pseudo-polynomial time and when not including the costs, in polynomial time. We develop filtering rules based on existing dynamic programming algorithms, exploiting the above mentioned time decomposition for difficult instances. In a numerical study, we compare several formulations of the problem: mixed integer linear programming, constraint programming and dynamic programming. We show that our global constraint is able to find solutions, unlike the decomposed constraint programming model and that constraint programming can be competitive, in particular when adding combinatorial side constraints.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper formulates the capacitated single-item lot-sizing problem (with time-varying production/inventory bounds and costs consisting of holding, unitary production, and setup terms) as a global constraint. It derives a new lower bound via a time decomposition, proves that bound consistency is enforceable in pseudo-polynomial time (polynomial time when costs are omitted), develops filtering rules that exploit existing DP algorithms together with the decomposition, and reports numerical comparisons of MILP, standard CP, and the new global constraint, claiming the latter finds feasible solutions where a decomposed CP model fails and remains competitive when combinatorial side constraints are added.

Significance. If the consistency and filtering claims hold, the work supplies a practical global constraint for a well-studied NP-hard problem that can be combined with other combinatorial constraints, as the experiments illustrate. The time-decomposition lower bound and the polynomial-time result without costs are technically interesting contributions; the experimental demonstration that the global constraint succeeds where a decomposed model does not is a concrete strength.

minor comments (3)
  1. [Problem formulation] The problem statement and notation for time-varying lower/upper bounds on production and inventory, as well as the three cost components, would benefit from a single consolidated table or explicit listing early in the manuscript to improve readability.
  2. [Numerical study] In the numerical study, the description of instance generation, parameter ranges, and the precise definition of 'difficult instances' should be expanded so that the reported run-time and solution-quality comparisons can be reproduced exactly.
  3. [Filtering rules] A brief statement of the precise complexity of the filtering algorithm (including the dependence on the magnitude of capacities and demands) would clarify the pseudo-polynomial claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its technical contributions, and the recommendation for minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No circularity: independent time decomposition and DP-based filtering

full rationale

The paper derives a new lower bound via an explicit time decomposition and encodes the lot-sizing problem as a global constraint whose bound consistency is achieved by adapting existing dynamic programming algorithms. No step reduces by definition to its own output, no fitted parameter is relabeled as a prediction, and no load-bearing uniqueness theorem or ansatz is imported via self-citation. The central filtering claim rests on the stated validity of the decomposition, which is presented as a novel construction rather than presupposed by the result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the approach relies on standard concepts from constraint programming and dynamic programming without introducing new fitted constants or postulated objects.

pith-pipeline@v0.9.0 · 5696 in / 1047 out tokens · 18100 ms · 2026-05-25T09:12:29.545347+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Aggarwal and J

    A. Aggarwal and J. K. Park. Improved algorithms for economic lot size problems. Operations Research, 41(3):549–571, 1993

    work page 1993

  2. [2]

    R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. pages 93–192, 1993

    work page 1993

  3. [3]

    Atamtürk and S

    A. Atamtürk and S. Küçükyavuz. AnO(n2) algorithm for lot sizing with inventory bounds and fixed costs.Operations Research Letters, 36(3):297– 299, 2008

    work page 2008

  4. [4]

    Atamtürk and J

    A. Atamtürk and J. C. Muñoz. A study of the lot-sizing polytope.Mathe- matical Programming, 99(3):443–465, 2004

    work page 2004

  5. [5]

    Barany, T

    I. Barany, T. J. Van Roy, and L. A. Wolsey. Strong formulations for multi- item capacitated lot sizing.Management Science, 30(10):1255–1261, 1984

    work page 1984

  6. [6]

    Beldiceanu and M

    N. Beldiceanu and M. Carlsson. Revisiting the cardinality operator and introducing the cardinality-pathconstraint family. InInternational Confer- ence on Logic Programming, pages 59–73. Springer, 2001

    work page 2001

  7. [7]

    G. R. Bitran and H. H. Yanasse. Computational complexity of the capaci- tated lot size problem.Management Science, 28(10):1174–1186, 1982

    work page 1982

  8. [8]

    Encod- ings of the sequence constraint

    S.Brand, N.Narodytska, C.-G.Quimper, P.Stuckey, andT.Walsh. Encod- ings of the sequence constraint. InInternational Conference on Principles and Practice of Constraint Programming, pages 210–224. Springer, 2007

    work page 2007

  9. [9]

    Federgruen and M

    A. Federgruen and M. Tzur. A simple forward algorithm to solve gen- eral dynamic lot sizing models with n periods inO(n logn) or O(n) time. Management Science, 37(8):909–925, 1991

    work page 1991

  10. [10]

    Feillet, P

    D. Feillet, P. Dejax, M. Gendreau, and C. Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Appli- cation to some vehicle routing problems.Networks, 44(3):216–229, 2004

    work page 2004

  11. [11]

    Florian and M

    M. Florian and M. Klein. Deterministic production planning with concave costs and capacity constraints.Management Science, 18(1):12–20, 1971

    work page 1971

  12. [12]

    Florian, J

    M. Florian, J. K. Lenstra, and A. Rinnooy Kan. Deterministic production planning: Algorithms and complexity.Management science, 26(7):669–679, 1980. 26

    work page 1980

  13. [13]

    Hellion, F

    B. Hellion, F. Mangione, and B. Penz. A polynomial time algorithm for the single-item lot sizing problem with capacities, minimum order quantities and dynamic time windows. Operations Research Letters, 42(8):500–504, 2014

    work page 2014

  14. [14]

    Hellion, F

    B. Hellion, F. Mangione, and B. Penz. Stability contracts between supplier and retailer: a new lot sizing model.International Journal of Production Research, 53(1):1–12, 2015

    work page 2015

  15. [15]

    J. N. Hooker. Operations research methods in constraint programming. In F. Rossi, P. van Beek, and T. Walsh, editors,Handbook of Constraint Programming, chapter 15, pages 27–68 – – 205–239. Elsevier, 2006

    work page 2006

  16. [16]

    V. R. Houndji, P. Schaus, and L. Wolsey. The item dependent stockingcost constraint. Constraints, pages 1–27, 2019

    work page 2019

  17. [17]

    V. R. Houndji, P. Schaus, L. A. Wolsey, and Y. Deville. The stockingcost constraint. In Principles and Practice of Constraint Programming, pages 382–397. Springer, 2014

    work page 2014

  18. [18]

    Kleinberg and É

    J. Kleinberg and É. Tardos.Algorithm design. Pearson Education India, 2006

    work page 2006

  19. [19]

    Krarup and O

    J. Krarup and O. Bilde. Plant location, set covering and economic lot size: an o (mn)-algorithm for structured problems. Numerische methoden bei optimierungsaufgaben, 3:155–180, 1977

    work page 1977

  20. [20]

    M. Z. Lagerkvist and C. Schulte. Propagator groups. In Principles and Practice of Constraint Programming-CP 2009, pages 524–538. Springer, 2009

    work page 2009

  21. [21]

    S. F. Love. Bounded production and inventory models with piecewise con- cave costs.Management Science, 20(3):313–318, 1973

    work page 1973

  22. [22]

    Pochet and L

    Y. Pochet and L. A. Wolsey.Production planning by mixed integer pro- gramming. Springer Science & Business Media, 2006

    work page 2006

  23. [23]

    Prud’homme, J.-G

    C. Prud’homme, J.-G. Fages, and X. Lorca.Choco Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S., 2016

    work page 2016

  24. [24]

    Steiger, W.-J

    R. Steiger, W.-J. van Hoeve, and R. Szymanek. An efficient generic network flow constraint. In Proceedings of the 2011ACM Symposium on Applied Computing, pages 893–900. ACM, 2011

    work page 2011

  25. [25]

    Tarim and I

    A. Tarim and I. Miguel. Echelon stock formulation of arborescent dis- tribution systems: An application to the wagner-whitin problem. InIn- ternational Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pages 302–318. Springer, 2004. 27

    work page 2004

  26. [26]

    Van Den Heuvel and A

    W. Van Den Heuvel and A. P. Wagelmans. Four equivalent lot-sizing mod- els. Operations Research Letters, 36(4):465–470, 2008

    work page 2008

  27. [27]

    Van Hoesel and A

    S. Van Hoesel and A. P. M. Wagelmans. An O(T3) algorithm for the economiclot-sizingproblemwithconstantcapacities. Management Science, 42(1):142–150, 1996

    work page 1996

  28. [28]

    Van Vyve, L

    M. Van Vyve, L. A. Wolsey, and H. Yaman. Relaxations for two-level multi-item lot-sizing problems.Mathematical Programming, 146(1-2):495– 523, 2014

    work page 2014

  29. [29]

    Wagelmans, S

    A. Wagelmans, S. Van Hoesel, and A. Kolen. Economic lot sizing: an O(n logn) algorithm that runs in linear time in the wagner-whitin case. Operations Research, 40:S145–S156, 1992

    work page 1992

  30. [30]

    H. M. Wagner and T. M. Whitin. Dynamic version of the economic lot size model. Management science, 5(1):89–96, 1958

    work page 1958

  31. [31]

    Zhang, S

    M. Zhang, S. Küçükyavuz, and H. Yaman. A polyhedral study of multiech- elon lot sizing with intermediate demands.Operations Research, 60(4):918– 935, 2012. 28

    work page 2012