--- title: "Exact Two-Item Resource-Constrained Joint Replenishment and Its Independent-Cap Relaxation Gap" date: 2026-08-08 version: "1.2.0-candidate" doi: 10.5281/zenodo.21855894 pdf: https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/two_cap_integrality_gap.pdf repository: https://github.com/ipitchford/certified-two-item-jrp archive: https://zenodo.org/records/21855894 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # Exact Two-Item Resource-Constrained Joint Replenishment and Its Independent-Cap Relaxation Gap ## Summary Joint replenishment asks when several items should be ordered together so that they can share a common ordering, dispatch, receiving, or changeover cost. Even with only two items, the exact objective is arithmetically delicate: periodic schedules coincide when their period ratio is rational, and the density of shared order epochs depends on the coprime numerator and denominator. This candidate turns that two-item problem into an auditable certificate system. Each fixed coprime ratio becomes a one-dimensional convex scale problem. A resource-aware Lagrange-dual bound then lower-bounds every ratio not yet enumerated. The paper proves that when the common ordering cost is positive, some rational synchronised policy is strictly better than the best desynchronised policy. The improving tail therefore eventually rises above the best enumerated cost and the algorithm terminates after finitely many ratios. “Guaranteed termination” has a precise and limited meaning here. It says the mathematical algorithm eventually returns a certificate on every instance in the stated model. It does not give a polynomial running-time bound, solve the multi-item problem, or remove the known number-theoretic difficulty of two-item joint replenishment. The release also studies the gap of the standard convex relaxation, denoted $(P)$. A cap-reduction theorem shows that, over nonnegative real resource systems, worst-case gap analysis can be restricted to separate item-frequency caps. For two items with independent caps, the new companion paper determines the exact supremum: $$ \Gamma_{2,\mathrm{box}}=\gamma, \qquad 1.111889593939396<\gamma<1.111889593940297. $$ The canonical triple-tie family attains the lower bound. A four-policy envelope, a symbolic critical interval, and a complete 212-cell exact rational outer cover prove the matching upper bound. This does **not** determine the unrestricted multi-item gap $\Gamma_P$. > **Status:** unrefereed candidate computer-assisted result. Producer-side fresh-extraction replay and solver-independent certificate checks pass. There is no independent reproduction, formal proof-assistant verification, external specialist review, peer review, field validation, complete novelty audit, or evidence of realised operating savings. ## Summary for specialists Let item $i$ use period $T_i>0$, with item-specific cost $K_i/T_i+H_iT_i$ and common cost $K_0$ at every distinct order epoch. Resource row $d$ requires $$ \frac{\alpha_{1d}}{T_1}+\frac{\alpha_{2d}}{T_2}\leq\beta_d, \qquad \alpha_{id}\geq0,\quad\beta_d>0. $$ For $T_2/T_1=p/q$ in lowest terms, set $T_1=qt$ and $T_2=pt$. The union density of the two order lattices is $(p+q-1)/(pqt)$, so the exact objective becomes $$ g_{pq}(t)=\frac{A_{pq}}{t}+B_{pq}t, $$ where $$ A_{pq}=K_0\frac{p+q-1}{pq}+\frac{K_1}{q}+\frac{K_2}{p}, \qquad B_{pq}=H_1q+H_2p, $$ on an exactly computable rational interval $t\geq t_{pq}^{\min}$. Its optimum is therefore rational or of the form $2\sqrt z$ with rational $z$. The constrained desynchronised optimum in frequency variables $f_i=1/T_i$ is $$ M_R=\min_{Af\leq\beta} \left[(K_0+K_1)f_1+\frac{H_1}{f_1}+(K_0+K_2)f_2+\frac{H_2}{f_2}\right]. $$ For every nonnegative multiplier vector $\lambda$, the package certifies $$ L(\lambda)=2\sum_{i=1}^{2} \sqrt{H_i\left(K_0+K_i+\sum_d\lambda_d\alpha_{id}\right)} -\sum_d\lambda_d\beta_d\leq M_R. $$ After all coprime pairs with $p+q\leq S$ are enumerated, every omitted rational or irrational ratio costs at least $$ \sqrt{\frac{S}{S+1}}\,M_R, $$ and the same statement remains certified with any stored dual lower bound $L(\lambda)$. The verifier checks nonnegative rational multipliers and downward dyadic radical bounds using integer arithmetic. The strict synchronisation theorem handles an irrational minimiser of $M_R$ with one-sided continued-fraction approximants. The separable perturbation is $O(q^{-2})$, while the newly created intersection saves common cost of order $q^{-1}$. A rational feasible policy is therefore eventually strictly cheaper than $M_R$. This supplies totality without implying efficient worst-case bit complexity. ## The exact two-item cap gap The canonical construction normalises $K_0=1$, sets $K_1=K_2=0$, imposes frequency caps $f_1\leq x$ and $f_2\leq1$, and chooses $$ H_1=\frac23, \qquad H_2=\frac{-3x^2+7x-2}{3(1-x)}. $$ On the certified interval $0.7509\leq x\leq0.751$, the ratios $(1,1)$, $(1,2)$, and $(2,3)$ tie and every other ratio is excluded by exact finite checks plus the resource-aware tail. The gap function is $$ G(x)=\frac{x(3x^2-5)}{3x^3-4x^2+x-2}. $$ Its unique family maximum occurs at the relevant root of $$ 6x^4-18x^3+19x^2-5=0, $$ and the corresponding $\gamma$ satisfies $$ 262\gamma^4-916\gamma^3+863\gamma^2+150\gamma-375=0. $$ For the matching upper bound, every normalised cap ratio is covered by four feasible policy families. Outside the critical interval $[149/200,151/200]$, the verifier checks a complete 212-cell rational cover and proves coefficientwise domination using exact arithmetic. Inside that interval, the symbolic quartic comparison closes the remaining case. The stored minimum outer slack is $$ \frac{3088515039309}{31027700000000000000}>0. $$ A separate 2,829-cell rational certificate gives the coarser bound $\Gamma_{2,\mathrm{box}}<1.11189$ by a differently generated cover. This is a producer-side cross-check, not independent reproduction. The release also includes a nearby fully rational instance with exact gap $$ \frac{2484309748962090917667}{2234313336955730917667} =1.111889593939846\ldots, $$ closing at $S=8$ after 21 coprime ratios. The exact equality is asserted for nonnegative real cost coefficients. The construction allows zero item-specific setup costs, exactly as the declared model does; it does not claim the same equality under a convention requiring every $K_i$ to be strictly positive or for rational data without a separate continuity argument. ## What the result does not establish - It does not determine the unrestricted multi-item gap of relaxation $(P)$; only the real-coefficient two-item independent-cap gap is closed. - The cited upper bound is conditional on the external theorem applying to the same relaxation and model. - It does not give a polynomial-time algorithm in binary input length. - It does not solve the multi-item joint replenishment problem. - The finite alignment-configuration hull is a two-item regression prototype, not a multi-item separation oracle or rounding theorem. - It proves no $k=1$, $k=2$, or fixed-column-sparsity approximation or hardness frontier. - It supplies no complete three-item exact oracle. - It does not model uncertain demand, safety stock, lead times, case packs, routing, phases, fixed delivery calendars, pointwise capacity, or multi-echelon interactions. - Synthetic screening and sensitivity outputs are not operational evidence. - A local replay receipt, DOI, or agreement among producer-workflow agents is not independent mathematical verification or peer review. ## Why the resource-aware tail matters An unconstrained tail can be far below the true cost when capacity or minimum-interval rows force the periods away from their unconstrained scales. The new dual bound keeps those rows in the stopping certificate. This sharply reduces the closing cutoff on the bundled instances while also supporting the proof that the unbounded algorithm eventually stops. The distinction is useful beyond implementation. A finite certificate proves a particular instance after a particular enumeration. The totality theorem explains why the same method will eventually certify every instance in the stated class. Neither fact establishes a polynomial running time. ## Who should care, and why | Audience | Potential use | Required caution | |---|---|---| | Inventory and operations-research theorists | Audit a compact exact two-item oracle and a new relaxation-gap construction. | The global gap and wider approximation frontier remain open. | | Algorithm designers | Use resource-dual tails as stronger finite stopping certificates. | Solver-independent replay is still producer-side and is not a complexity bound. | | Planning-system developers | Benchmark two-item heuristic outputs against exact rational/radical certificates. | The model uses stationary average-rate constraints and omits many operational details. | | Approximation researchers | Reuse the cap reduction, four-policy envelope, and exact two-item cap constant as regression targets. | The two-item upper certificate is not a multi-item upper certificate. | | Formal-methods researchers | Formalise the fixed-ratio, scale-floor, synchronisation, cap-reduction, and elimination arguments. | No theorem is currently proof-assistant checked. | | AI research agents | Retrieve exact claims, exclusions, manifests, replay commands, proof objects, and open tasks. | Preserve the candidate status and every non-inference boundary. | | Independent reviewers | Reconstruct the analytic proof and certificate semantics from the immutable archive. | Producer adversarial review is not an external specialist audit. | ## The extension programme remains open The supplied extension document is preserved in the release and mapped requirement by requirement. This candidate completes the exact two-item resource-aware tail, totality theorem, real-coefficient cap reduction, exact two-item independent-cap gap, stronger algebraic family, and a finite local alignment prototype. It deliberately leaves later stages as separately publishable work: 1. determine whether the unrestricted multi-item gap equals the two-item cap constant $\gamma$; 2. build a multi-item alignment relaxation with separation and rounding; 3. determine the column-sparsity approximation or hardness frontier; 4. construct and independently reproduce a complete three-item oracle; 5. replace one-at-a-time sensitivity with correlated uncertainty regions; 6. add phases, calendars, and pointwise constraints; 7. run a bounded, preregistered field pilot; and 8. develop a more general constrained periodic-synchronisation theory. ## How the package was checked The immutable release ZIP was rebuilt and replayed from a fresh extraction on macOS arm64 with pinned Python dependencies and a recorded TeX toolchain. The positive controls rebuild four finite witnesses, verify two parametric families, regenerate and verify both two-cap certificates, check the alignment regression, regenerate numerical outputs and six figures, run 17 tests, compile the code, and rebuild both 8-page papers and the 3-page practitioner brief. The negative controls re-hash and require rejection of a finite-witness gap mutation, a two-cap upper-bound mutation, and an exact claim-scope mutation. A deliberately truncated solve must exit with status 2 and omit every optimum-named field. The release gate also runs under `python -O` so a verifier depending only on disabled `assert` statements cannot silently pass. These checks establish the declared byte, execution, and certificate facts for the archived payload. They do not establish independent reproduction, the truth of every conventional proof step, formal verification, novelty, specialist acceptance, field validity, or operational benefit. ## What is in the evidence package The [public GitHub repository](https://github.com/ipitchford/certified-two-item-jrp) contains both candidate papers and TeX sources, the practitioner brief, exact solver, standard-library certificate verifiers, four finite witnesses, family and two-cap certificates, the alignment prototype, tests, schemas, figures, outputs, claim and AI indexes, provenance, assurance and licence records, the complete extension programme, and its requirement-to-evidence ledger. The immutable candidate is tag [`v1.2.0-candidate`](https://github.com/ipitchford/certified-two-item-jrp/releases/tag/v1.2.0-candidate), commit `b31ef2c15dcf184638c1b3d9f0730c12a8ed54cf`. Its validated ZIP has SHA-256 `a1103de05bf1793119fd005d4685e161aca8aafcb6fea71e67f63f6fb0a82b13`. The [producer replay receipt](https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/certified-two-item-jrp-v1.2.0-candidate.replay-receipt.json) and [full replay log](https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/fresh-replay.log) are external to the ZIP so that they can identify the archive without a circular self-hash. The preserved version is [Zenodo record 21855894](https://zenodo.org/records/21855894), DOI [10.5281/zenodo.21855894](https://doi.org/10.5281/zenodo.21855894). The [exact two-item cap-gap paper](https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/two_cap_integrality_gap.pdf), [certification-and-termination paper](https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/certified_two_item_jrp.pdf), and [practitioner brief](https://github.com/ipitchford/certified-two-item-jrp/releases/download/v1.2.0-candidate/practitioner_brief.pdf) are separately downloadable. Software is MIT licensed. Original non-software papers, documentation, data, certificates, metadata, figures, and release material are dedicated under CC0-1.0 to the extent the publisher holds the relevant rights; third-party literature, dependencies, names, and embedded fonts remain outside that dedication. ## Open directions for follow-up research - Determine the unrestricted multi-item integrality gap and whether it equals the now-certified two-item independent-cap constant gamma. - Construct a multi-item alignment-aware relaxation with polynomial separation and a rounding theorem while preserving the exact two-item regression suite. - Classify the column-sparsity k=1, k=2, and fixed-k approximation or hardness frontier. - Build and independently reproduce a complete exact three-item oracle, including its regime and tail proof objects. - Develop robust correlated-uncertainty regions rather than one-at-a-time sensitivity analysis. - Extend the model to calendar phases, fixed delivery dates, and pointwise capacity without erasing synchronisation semantics. - Run a preregistered field pilot with reconciled marginal costs, operational feasibility gates, guardrails, and stop rules. - Obtain independent mathematical reconstruction, specialist review, proof-assistant formalization, and a broader novelty and priority audit. ## Verification status Unrefereed candidate computer-assisted result. Producer-side solver-independent replay, fresh-extraction regeneration, mutation controls, fail-closed output checks, deterministic document builds, GitHub/Zenodo archive matching, and public file readback pass. The analytic manuscript and supplied certificates have not been independently reconstructed by an unaffiliated party or formalized in a proof assistant. There has been no external specialist audit, editorial peer review, field validation, complete novelty or priority audit, or demonstration that a certified nominal policy yields operational savings. The exact global relaxation gap, multi-item alignment relaxation and rounding, column-sparsity frontier, three-item oracle, robust uncertainty, calendar phases, pointwise capacity, and wider theory remain open. ## Sources and related work - Wildeman, R. E., Frenk, J. B. G., & Dekker, R. (1997). An efficient optimal solution method for the joint replenishment problem. European Journal of Operational Research, 99, 433-444. - Porras, E., & Dekker, R. (2006). An efficient optimal solution method for the joint replenishment problem with minimum order quantities. European Journal of Operational Research, 174, 1595-1615. - Porras, E., & Dekker, R. (2008). A solution method for the joint replenishment problem with correction factor. International Journal of Production Economics, 113, 834-851. - Schulz, A. S., & Telha, C. (2024). Integer factorization: Why two-item joint replenishment is hard. Operations Research, 72, 1192-1202. - Segev, D. (2025). The continuous-time joint replenishment problem: epsilon-optimal policies via pairwise alignment. Management Science, 71, 4183-4197. - Segev, D. (2026). Improved approximation guarantees for joint replenishment in continuous time. Mathematics of Operations Research, 51, 1683-1712. - Segev, D. (2026). Resource-constrained joint replenishment via power-of-m policies. arXiv:2603.18720v1. - Creemers, S., & Stephan, T. (2026). Special cases of the joint replenishment problem: A mathematical analysis. SSRN 6674418.