PaperlayerView exact revision on arXiv

Source-linked AI summary

Monge matrix searching for lot sizing with piecewise-concave production costs

Kleitos Papadopoulos

arXiv:2610.03277v1cs.DS

TL;DR

Piecewise-concave production and holding or backlog costs, along with stock-domain restrictions, complicate exact single-item lot sizing. The paper uses boundary-indexed dynamic programming tables and Monge matrix searches to obtain exact algorithms. Its 300-case timing comparison finds gains on larger uncapacitated tests but no universal practical superiority.

  • Problem

    Single-item lot sizing must accommodate piecewise-concave production and holding or backlog costs, including restricted production and stock domains.

    Source: §1 · p. 2

  • Method

    The algorithm decomposes solutions at stock-boundary levels and batches transitions by a designated production period into Monge searches over breakpoint-only prefix and suffix tables.

    Source: §1 · p. 3, §6 · pp. 31–32

  • Results

    All 300 no-backlogging benchmark objectives agree with the predecessor implementation and an inventory-state oracle; larger uncapacitated tests show gains, while many smaller and capacitated cases favor the predecessor.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The contribution is an exact reduction and a documented implementation comparison, not a claim of universal practical superiority.

    Source: §6 · p. 32

    Timing covers only the original model, not generalized models or stronger staircase routines, and the finite-horizon study does not establish asymptotic exponents or a general crossover horizon.

    Source: §4.6 · pp. 27–28

Abstract

from arXiv · show

We study single-item lot sizing with piecewise-concave production and holding--backlog costs over $T$ periods. Production has $m$ common positive finite breakpoints, and stock costs and domains have $K$ common finite boundary levels. For fixed $m,K$, we give an exact deterministic algorithm using $\OmK(T^{m+2}\alpha(T+2))$ arithmetic operations and a Las Vegas algorithm using $\OmK(T^{m+2})$ expected operations, where $\alpha$ is the inverse Ackermann function. The algorithms retain nonlinear concave cost pieces and cover backlogging, common-grid stock limits, and explicit terminal-stock policies. A structural decomposition at stock boundary levels yields breakpoint-only prefix and suffix tables. Batching transitions by a designated production period produces implicit matrices that are Monge double staircases on each production piece. Established matrix searches, merged state orders, and backward evaluation provide the bounds. A simpler rectangle/SMAWK variant requires $\OmK(T^{m+2}\log(T+2))$ operations. On 300 no-backlogging benchmark cases, its objectives agree exactly with the predecessor dynamic program and an inventory-state oracle. Geometric-mean paired time ratios are \GeoUncap\ for uncapacitated cases and \GeoCap\ for capacitated cases, with ratios above one favoring matrix searching. A 640-case base-model validation suite and a separate 624-case generalized-model suite pass. The timing study does not benchmark the generalized models or the stronger staircase routines. All bounds assume exact arithmetic, constant-time cost queries, and explicit closed-domain concavity conditions.

1. Introduction

Piecewise-concave lot sizing extends beyond globally concave production, while combining nonlinear production pieces with stock-boundary states creates a computational challenge. The paper gives an exact matrix-searching reduction and algorithms for this setting.

1. Introduction

  • Earlier work established polynomial solvability for fixed production breakpoints, but combining breakpoint schedules around the exceptional production period remained computationally difficult.Affine separability used in related piecewise-linear results does not directly apply to nonlinear concave production pieces.Source: §1 · p. 2
  • Fixing a designated production period yields Monge transition matrices on each concave production piece, with breakpoint-only prefixes and suffixes as states.The production needed is a_j−β_i, and the defined matrix entries form a double staircase; holding cost is a column offset.Source: §1 · pp. 2–3
  • The deterministic algorithm uses O_m,K(T^(m+2) α(T+2)) arithmetic operations, while the Las Vegas algorithm uses O_m,K(T^(m+2)) expected operations.Both bounds assume fixed m and K; the analysis does not claim bit-complexity or fixed-parameter tractability.Source: §1 · p. 3
  • The model admits nonlinear piecewise-concave production, backlogging, common stock-boundary levels, and explicit terminal-stock policies.Production capacities, minimum quantities, and multiple production regimes are represented through production domains.Source: §1 · pp. 2–3
  • The timing study compares the original no-backlogging specialization, while the generalized solver is validated separately and stronger staircase routines are not benchmarked.The introduction distinguishes the original timing experiment from generalized-model validation.Source: §1 · pp. 3–4

2. Problem definition and properties of optimal solutions

The model uses common production breakpoints and stock-boundary levels to specify piecewise-concave costs and feasibility, with terminal policies determining permitted final stock. Its optimal-solution structure supports exact algorithms through boundary intervals and breakpoint-only production schedules.

2.1. Production, signed stock, and cost domains

  • Stock may be negative to represent backlog, and stock costs are concave on supplied closed domains indexed by common boundary levels that include zero and initial stock.Finite inventory and backlog limits must be included in the boundary set and enforced through available domains.Source: §2.1 · pp. 4–5
  • Production costs are finite, nonnegative, and concave on supplied closed breakpoint intervals, rays, or singletons; unavailable production quantities lie outside the supplied domains.The finite pieces need not be affine, and production functions and available domains may vary by period.Source: §2.1 · pp. 4–5
  • The terminal sets distinguish clearing all stock and backlog, clearing backlog while allowing surplus, and permitting final backlog with its specified cost.These are distinct optimization problems; the terminal set is applied by restricting the effective final-period holding-cost domain.Source: §2.1 · p. 5

2.2. Notation and computational model

  • The operation bounds count exact arithmetic, comparisons, array access, and supplied cost evaluations, with constants depending on fixed m and K.They are not bit-complexity claims and do not assume constant-time manipulation of arbitrary symbolic representations.Source: §2.2 · p. 6

2.3. Existence of an optimum

  • Every feasible suffix starting at a stock boundary has a finite attained optimum under each terminal convention.Nonnegative costs and concave closed-domain restrictions provide a sufficient well-posedness condition.Source: §2.3 · pp. 6–7

2.4. Boundary intervals and exceptional production

  • An optimum exists with at most one production quantity outside the breakpoint set in each boundary interval, and a final tail ending off a stock boundary uses breakpoint productions only.With demands, production breakpoints, stock levels, and initial stock on a common lattice, an optimum can also be chosen on that lattice. A two-period example shows that a zero-boundary-only interval rule can miss the optimum when an intermediate stock boundary matters.Source: §2.4 · pp. 7, 9

3. An improved exact algorithm

The section presents an exact algorithm that decomposes schedules around a designated production period, uses breakpoint-only prefix and suffix cost tables indexed by stock boundaries, and searches batched transitions through partial Monge matrices while retaining nonlinear production costs and enforcing stock domains and terminal policies. Its implementable rectangle-search variant has a deterministic time bound with matching-order space usage.

3.1. Boundary-indexed prefix and suffix tables

  • O_m,K(T^{m+2}) time and space suffice for correct breakpoint-only prefix and suffix tables with minimizing production choices.The tables enforce each period's stock-domain tests, including terminal restrictions through the effective terminal cost.Source: §3.1 · pp. 10–11

3.2. An exact batched Bellman equation

  • Each admitted batched transition gives an exact feasible candidate, representing every boundary interval with at most one fractional production and evaluating its quantity with the original nonlinear cost oracle.The batched Bellman equation combines the transition minima with a breakpoint-only terminal alternative for each terminal convention.Source: §3.2 · pp. 12–13

3.3. Concavity and the partial Monge structure

  • Within each production domain, defined entries satisfy the Monge inequality, and feasible columns form row intervals with nonincreasing endpoints; padding undefined entries with infinity can invalidate search.Nonlinear holding costs add no row-column interaction because they are optimized in the tables or depend only on the column.Source: §3.3 · pp. 13–15

3.4. Searching a double staircase

  • A partial Monge batch with monotone row-interval endpoints decomposes into rising staircases with at most 2r row and 2c column occurrences, enabling deterministic O((r+c) alpha(r+c+2)) or expected O(r+c) search.The decomposition takes O(r+c) time and uses established staircase-search primitives.Source: §3.4 · pp. 15–16

3.5. Reusing sorted state orders

  • O_m,K(T^{m+2}) total time and space construct and reuse batch row and column orders by merging newly added states, avoiding independent full-batch sorting.The invariant universes include boundary labels and require neither integrality, distinct breakpoint sums, nor presorted input.Source: §3.5 · pp. 17–18

3.6. Backward evaluation, correctness, and complexity

  • Backward evaluation finalizes continuation values before each batch and returns the optimum or infinity exactly for infeasible instances, with witnesses recovering an optimal plan whenever feasible.A simpler segment-tree rectangle variant searches fully defined Monge rectangles with SMAWK in O((r+c) log(c+2)) deterministic time.Source: §3.6 · pp. 18–19, §3.7 · pp. 20–21
  • O_m,K(T^{m+2} alpha(T+2)) deterministic time and O_m,K(T^{m+2}) expected Las Vegas time solve every terminal variant, with O_m,K(T^{m+2}) worst-case space.The randomized algorithm is always correct; only its running time is random.Source: §3.6 · pp. 19–20

3.7. An implementable rectangle-search variant

  • Algorithm 3 runs in O_m,K(T^(m+2) log(T+2)) time and uses O_m,K(T^(m+2)) space.At one period, rectangle row-assignment lists use O_m,K(T^(m+2)) space and can then be discarded.Source: §3.7 · p. 21

4. Computational experiments

The experiments validate objective agreement for the original and generalized implementations, then compare the rectangle/SMAWK variant with the predecessor algorithm on the original model. Timing gains vary by setting and tested size, while the study leaves generalized-model speed and several broader performance questions unmeasured.

4.1. Original-model implementations and benchmark design

  • The benchmark compares R-SMAWK with a fresh KYA implementation across 300 cases; each (m,T) uses five seeds crossed with capacity and terminal-inventory conventions.Capped and uncapped families share demands and formula coefficients, but removing the production tail can change endpoint costs, so their comparison does not isolate capacity alone.Source: §4 · p. 21, §4.1 · pp. 22–23, Table 1 · p. 23

4. Computational experiments

  • Timing covers only the K=1 no-backlogging specialization with nonnegative inventory and zero or free nonnegative terminal stock; it does not benchmark the generalized implementation.The separate generalized-model study checks correctness rather than runtime, and neither it nor the timing study benchmarks the stronger staircase routines.Source: §4 · p. 22, §4.4 · p. 26

4.2. Timing protocol and record provenance

  • The archived timing protocol uses three runs per solver per case and replaces 108 missing observations for 18 incomplete cases with reruns under the same protocol.The final dataset contains 1,800 analyzed calls; missing times were not inferred from summaries.Source: §4.2 · pp. 23–24

4.3. Original-model exact-answer validation

  • All 300 benchmark cases have identical KYA and R-SMAWK objectives, confirmed by a separate exact inventory-state dynamic-programming oracle.The 640-case original-model suite also agrees throughout, including 132 infeasible cases, and reconstructed plans pass feasibility and exact-cost checks.Source: §4.3 · pp. 24–25

4.4. Generalized-model implementation and validation

  • All 624 generalized-model validation cases agree exactly with a finite inventory-state oracle, and all 585 finite reconstructed plans pass feasibility and exact-objective checks.The suite includes ordinary backlogging, piecewise-concave stock costs, stock and backlog limits, minimum production quantities, and terminal-policy variants.Source: §4.4 · pp. 25–26

4.5. Timing results

  • R-SMAWK is faster on 186 cases and KYA on 114; geometric-mean paired time ratios are 2.531 for uncapacitated cases, 1.006 for capacitated cases, and 1.595 overall.The capacitated aggregate is effectively tied, and larger tested capacitated cells favor R-SMAWK; smaller tested free-terminal groups favor KYA in all six series.Source: §4.5 · pp. 26–27, Table 3 · p. 26, Figure 2 · p. 29

4.6. Interpretation, limitations, and research workflow

  • The timing results are consistent with a trade-off between matrix-search setup work and avoided state combinations, but no ablation identifies the cause of any one optimization.The study uses m≤3, one synthetic family, one timed breakpoint grid per m, five seeds per cell, and three repetitions; finite horizons do not establish asymptotic exponents.Source: §4.6 · p. 27
  • Peak memory, reconstruction time, industrial instances, commercial solvers, compiled implementations, and independent group replication are outside the reported evaluation.The inventory oracle is independent in formulation, but the implementations share an AI-assisted development workflow.Source: §4.6 · pp. 27–28

5. Special cases and scope

The model and algorithm specialize to several stock, terminal-policy, and production-domain settings when the relevant common boundary levels are fixed. The stated limits exclude settings that violate the theorem’s assumptions.

5.1. Concave holding costs without backlogging

  • The original no-backlogging model uses zero initial stock, nonnegative inventory, and concave holding costs; either zero or free nonnegative terminal stock is allowed.The stated deterministic and expected bounds specialize to O_m(T^(m+2)α(T+2)) and O_m(T^(m+2)); rectangle searching adds a logarithmic factor.Source: §5.1 · p. 29

5.2. Backlogging

  • Ordinary backlogging allows stock on both half-lines with costs concave separately on each, and the same bounds apply when K=1.The terminal set specifies whether inventory and backlog are cleared, surplus is permitted, or final backlog is allowed.Source: §5.2 · pp. 29–30

5.3. Piecewise-concave stock costs and stock limits

  • Common holding-cost breakpoints, finite stock-domain limits, and period-dependent inventory or backlog limits are represented through stock boundary levels.For fixed K, these cases preserve the exponent of T in the main bounds.Source: §5.3 · p. 30

5.4. Production capacities, minimum quantities, and regimes

  • Common-grid production capacities, minimum order quantities, and production regimes are represented by restricting production domains or using finite breakpoints.Table 5 presents specializations for fixed stock-boundary count; its caption notes that rectangle implementation adds a logarithmic factor relative to the expected bound.Source: §5.4 · p. 30, Table 5 · p. 30

5.5. Affine production pieces

  • For affine production pieces, monotone deque processing maintains the minimum column score as window endpoints move monotonically.Endpoint values that differ from adjoining affine formulas require separate singleton searches and open affine interiors.Source: §5.5 · p. 31

5.6. Limits of the result

  • For fixed m and K, the result requires common production and stock boundary levels, closed-domain concavity, consistent endpoint values, and exact cost queries.Arbitrary holding functions, multiple items with shared capacities, and lost-sales decisions are outside the stated scope.Source: §5.6 · p. 31

6. Conclusions

The paper reduces nonlinear piecewise-concave lot sizing to piecewise-Monge transition searches, with boundary-labelled tables covering stock-cost and backlogging cases. Validation supports exact objectives, while the timing results show gains in some tested cases but not universal practical superiority.

6. Conclusions

  • Fixing a production period exposes piecewise-Monge transition matrices, while boundary-labelled prefix and suffix tables include backlogging and piecewise-concave holding costs.Reused orders and backward evaluation give deterministic O_{m,K}(T^(m+2)α(T+2)) and expected Las Vegas O_{m,K}(T^(m+2)) bounds.Source: §6 · pp. 31–32
  • All 300 no-backlogging benchmark objectives agree with both the predecessor implementation and an inventory-state oracle; separate validation suites also pass for the base and extended models.The extended implementation’s 624-case suite checks exact objectives and feasible-plan reconstruction, but supplies no timing evidence.Source: §6 · p. 32
  • The rectangle/SMAWK implementation has an additional logarithmic factor, and the documented timing comparison does not establish universal practical superiority.Larger uncapacitated tests show gains, while many smaller and capacitated cases favor the predecessor.Source: §6 · p. 32

Data and code availability

The reproducibility archive includes timed solvers, validation materials, raw timing records, and the generalized boundary-level solver and its case records.

Data and code availability

  • The archive contains both timed solvers, the inventory-state oracle, serialized instances, raw timing records, validation programs, and source fingerprints.It also includes the boundary-level solver and its 624 case records; the archive does not implement the Klawe–Kleitman or Chan staircase algorithms.Source: Data and code availability · p. 32

Declaration of generative AI and AI-assisted technologies in the manuscript preparation

The manuscript reports use of ChatGPT in developing and editing mathematical exposition, literature positioning, code, source, and presentation of computational results.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation

  • ChatGPT was used to develop and edit mathematical exposition, literature positioning, code, LaTeX source, and computational-results presentation.Its research role is described in Section 4.6.Source: process · p. 33
Loading 2610.03277v1…