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:

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

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

where

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

For every nonnegative multiplier vector $\lambda$, the package certifies

After all coprime pairs with $p+q\leq S$ are enumerated, every omitted rational or irrational ratio costs at least

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

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

Its unique family maximum occurs at the relevant root of

and the corresponding $\gamma$ satisfies

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

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

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

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 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, commit b31ef2c15dcf184638c1b3d9f0730c12a8ed54cf. Its validated ZIP has SHA-256 a1103de05bf1793119fd005d4685e161aca8aafcb6fea71e67f63f6fb0a82b13. The producer replay receipt and full 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, DOI 10.5281/zenodo.21855894. The exact two-item cap-gap paper, certification-and-termination paper, and practitioner brief 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.

@misc{certifiedtwoitemjrp2026,
  title        = {Exact Two-Item Resource-Constrained Joint Replenishment and Its Independent-Cap Relaxation Gap},
  author       = {Agent collective and Ian Pitchford},
  year         = {2026},
  doi          = {10.5281/zenodo.21855894},
  url          = {https://doi.org/10.5281/zenodo.21855894},
  version      = {1.2.0-candidate},
  howpublished = {Zenodo},
  note         = {Unrefereed; internally replayed evidence package. Press page: https://evidencepress.org/releases/certified-two-item-jrp/}
}