CS Paper Radar

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

Kleitos Papadopoulos

cs.DS ·submitted 2026-10-02 13:20 UTC · v1
benchmarkunusual

Abstract

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}α(T+2))$ arithmetic operations and a Las Vegas algorithm using $\OmK(T^{m+2})$ expected operations, where $α$ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds

cs.DS ·2026-10-16 ·Kleitos Papadopoulos
theory similarity 0.63
Abstract

We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds. Unit prices may vary arbitrarily over time. For one common positive discount threshold, we give an exact algorithm requiring $O(n^3)$ arithmetic operations and $O(n^2)$ working space, including recovery of an optimal purchase plan. The method combines a critical-state theorem in cumulative-purchase coordinates with two prefix-minimum scans per dynamic-programming layer. The structural argument accommodates downward price discontinuities and distinguishes prescribed from free terminal inventory. With a fixed global set of $m$ positive threshold values, the bounds become $O_m(n^{m+2})$ time and $O_m(n^{m+1})$ space. Period-specific thresholds admit the same exact construction, but its state set can be exponential. For commensurate flow data, an inventory-lattice implementation takes $O(PW)$ time, where $P$ is the total number of price tiers and $W$ is the largest inventory-lattice width. We also derive a conditional optimality certificate from a monotone one-threshold relaxation; this certificate does not imply a near-linear worst-case algorithm for arbitrary prices. Exact-arithmetic implementations are checked against exhaustive inventory dynamic programs and tier-enumeration linear programs. An illustrative timing study identifies settings in which the lattice implementation is preferable.

0.23

An $O(n\log n)$ Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

cs.CE ·2026-11-17 ·Kleitos Papadopoulos
similarity 0.62
Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold $Q > 0$ for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of $Q$. We give an exact $O(n\log n)$-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using $O(n)$ working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in $O(n\log n)$ time and $O(n\log n)$ space.

0.26

Entropic Column Generation and Lehmer Branch-and-Price for Bin Packing Problem

cs.DM math.OC ·2026-10-31 ·Masoud Ataei
benchmarkcode/data similarity 0.59
Abstract · 38 pages, 1 figure, 8 tables. Code: https://github.com/chimera1001/lehmer-bp

We introduce Lehmer branch-and-price, an exact algorithm for bin packing and cutting stock problems built on the Lehmer transform, the ratio of Mellin transforms of item weights at consecutive orders. The transform maps each bin, a finite multiset of item weights, to a smooth increasing curve, and so gives the discrete problem a continuous representation on which the tools of analysis, such as convexity, exponential families and smoothing, can act. Read along this curve, the problem yields an explicit dual solution, a monotone representation of the dominance order, a family of constructive heuristics with first fit decreasing as its limit, and an integer identity that tells when the linear relaxation can decide an instance and when only a perfect packing can improve the best solution known. Lifted from items to patterns, the transform gives entropic column generation, a new form of column generation that bounds the relaxation from both sides at every iteration without solving the pricing problem exactly, maximizes a smoothed dual at an explicit rate, and measures by an entropy how much the relaxation leaves undecided. We show that the proposed algorithm outperforms the state-of-the-art methods on the standard benchmark in both the number of instances solved and the computational time.

0.40

Grid Theory and Polynomiality in Dynamic Lot-Sizing

cs.DM math.OCcs.DSmath.CO ·2026-10-02 ·El-Mehdi Mehiri, Nabil Absi, Elodie Suzanne
theory similarity 0.53
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.

0.27

A faster matrix multiplication algorithm through structured optimization

cs.DS cs.CC ·2026-10-06 ·Reza Zadeh
similarity 0.53
Abstract

We present a new asymptotic matrix multiplication construction yielding $ω<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic operations over the rationals, reals, or complex numbers. The construction improves the bound $2.371177$ of Dupont et al. within the combination-loss framework for the Coppersmith--Winograd tensor. Our approach combines a shared recursive parameter family with a conditioned optimization procedure that addresses two obstacles: weak gradients at low-mass constituents and competing bottlenecks in the retained exponent. A mass- and probability-dependent rescaling supports quasi-Newton optimization in $212\,820$ coordinates, while a six-control correction balances the three extraction roles at each relevant stage. Positive rational entropy-dual factors and an independent ordinary-string verifier turn the resulting construction into an exact certificate. The verified upper-bound expression lies in $[2.3711592385931075066123,\,2.3711592385931075066124]$. The complete witness and an offline verifier using only the Python standard library accompany the paper.

0.21

A 5/3 Guarantee for Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems

cs.DS math.OC ·2026-09-06 ·Ming Hu
benchmarktheory similarity 0.52
Abstract · 32 pages of main text and references, plus a 32-page online appendix; 6 figures

Fixed shipment costs encourage large orders, while inventory and customer backlog costs favor frequent replenishment. In a serial system, the stages must also coordinate their lot sizes and material availability. We study the classical echelon stock $(R,nQ)$ policy: the downstream stage requests a fixed lot, the upstream stage orders an integer multiple of that lot, and transfers contain complete lots. For unit Poisson demand, deterministic lead times, setup and holding costs at both stages, and full backlogging, we prove that the optimized cost in this class is at most $5/3\approx1.667$ of the optimal admissible system cost, uniformly over all nonnegative cost rates, demand rates, and lead times. The guarantee holds even when the selected policy pays a setup charge for every lot while the optimal benchmark pays only once per aggregate shipment. To obtain the guarantee, we use a common inventory calculation that allows independently chosen replenishment frequencies while respecting upstream material availability. We compare its optimized value, an upper bound on the best integer-ratio policy cost, with a novel lower bound on the optimal system cost that combines allocated single-stage costs with the minimum inventory cost when setup costs are zero. We also show that no uniform factor below $(1+\sqrt{3})/2\approx1.366$ is possible for the classical class. Existing numerical experiments place best-found classical policies within $22.7\%$ of an evaluated lower bound across three broad grids. The results quantify both the reliability and the limits of a simple operating rule and explain how shipment consolidation, replenishment timing, and flexibility affect its value.

0.26

A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks

cs.DS ·2026-10-17 ·Siyuan Chen, Suixiang Gao, Zheyu Jiang, Wenguo Yang
similarity 0.52
Abstract · 23 pages

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\varepsilon)(nk+1)^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\varepsilon)$ depends only on $d$ and $\varepsilon$, and $H=O(d \log(2d) / \varepsilon^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

0.21

A Note on Truly Subquadratic Time FPTAS for Knapsack

cs.DS ·2026-11-17 ·Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
similarity 0.51
Abstract

We show that an $\widetilde{O}(m^ρ)$-time algorithm for integer $(\min,+)$-convolution, where $1<ρ<2$, gives a randomized fully polynomial-time approximation scheme for $0$--$1$ Knapsack running in $\widetilde{O}(n+(1/ε)^{1+ρ/2})$ time. The algorithm returns a feasible solution whose profit is at least the optimum divided by $1+ε$, with high probability. We use the all-capacities proximity decomposition of Chen, Lian, Mao, and Zhang. Its two quadratic computations are replaced by blocked computation of requested prefix and suffix functions, and exact computation within groups sharing one of Chan's profit grids. Thus the approximation scheme retains half of the saving in the convolution exponent. Wang's weighted-cache 3SUM bound, transferred to witnessed integer convolution by Zhou, gives the numerical bound $\widetilde{O}(n+(1/ε)^{1.981})$.

0.21