Eq. (23) — LD1 = max over (β, λ, μ) of z(RF-bar) is a valid lower bound on the 2E-CVRP
ProvedTwoEchelonCVRP.LowerBound.ld1_lower_boundConsider a 2E-CVRP instance with positive demands and route families , . Let , for every satellite , , and let satisfy the penalty system (12). Then for every feasible solution of formulation ,
Equivalently, the quantity
is a valid lower bound on the 2E-CVRP, and so is every value of reached along the way.
This is the lower bound that the paper's bounding procedure DP¹ computes, and on which its route elimination and its configuration enumeration rest.
Formalization Note The bound is stated for every admissible , which is equivalent to and avoids defining the maximum. is an infimum in the extended reals. The paper derives the bound from Theorem 1 and Theorem 3; Theorem 3 as printed is false (see the corrected milestone), but the bound itself holds because the solutions induced by feasible solutions of respect the second-level fleets. Positive demands are needed: with a zero-demand customer the bound fails.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF import Definitions.Def_TwoEchelonCVRP_LowerBound_RFbar
namespace TwoEchelonCVRP.LowerBound
/-- Eq. (23) with Theorems 1 and 3 (pp. 301–302): `LD1 = max_{β,λ,μ} z(RF-bar(β, λ, μ))` is a valid
lower bound on the 2E-CVRP, i.e. for every solution `β` of (12) and every `λ`, `μ ≤ 0`, `μ_0 ≤ 0`,
`z(RF-bar(β, λ, μ))` is at most the cost of every feasible solution of F. -/
theorem ld1_lower_bound (I : Instance) (RS : RouteSystem I)
(β : Fin I.nc → Fin I.ns → ℝ) (lam : Fin I.nc → ℝ) (μ : Fin I.ns → ℝ) (μ0 : ℝ)
(hμ : ∀ k, μ k ≤ 0) (hμ0 : μ0 ≤ 0) (hβ : SatisfiesPenalty RS β lam μ μ0)
(s : SolF RS) (hs : IsFeasibleF RS s) :
zRFbar RS β lam μ μ0 ≤ ((costF RS s : ℝ) : EReal) := by sorry
end TwoEchelonCVRP.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.