Theorem 3 (corrected) — z(RF-bar) is at most the RF cost of every RF solution respecting the second-level fleets
ProvedTwoEchelonCVRP.LowerBound.theorem_3Consider a 2E-CVRP instance with positive demands and route families , , and let , , , be arbitrary real vectors. Let be a feasible solution of whose satellite loads respect the second-level fleets:
Then
Every solution induced by a feasible solution of satisfies the load condition, so this is the form in which the paper uses Theorem 3: combined with Theorem 1 it gives the lower bound LD1.
Formalization Note The paper states for every solution of (12). As printed this is false: does not limit a satellite's load by , while the loads in are capped by . With one satellite, two customers of demand 1, , , , , is feasible but , so . The load hypothesis is the correction. Neither (12) nor the signs of are needed, so they are not assumed. Optimal values are infima in the extended reals.
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF import Definitions.Def_TwoEchelonCVRP_LowerBound_RFbar
namespace TwoEchelonCVRP.LowerBound
/-- Theorem 3 (p. 302), corrected: `z(RF-bar(β, λ, μ))` is at most the objective (13) of every
feasible solution of RF whose satellite loads satisfy `∑_i q_i ξ_{ik} ≤ m_k Q_2`. (As printed,
without the load condition, the inequality `z(RF-bar) ≤ z(RF)` fails.) -/
theorem theorem_3 (I : Instance) (RS : RouteSystem I)
(β : Fin I.nc → Fin I.ns → ℝ) (lam : Fin I.nc → ℝ) (μ : Fin I.ns → ℝ) (μ0 : ℝ)
(σ : SolRF RS) (hσ : IsFeasibleRF RS σ) (hload : ∀ k, σ.load k ≤ I.m k * I.Q2) :
zRFbar RS β lam μ μ0 ≤ ((objRF RS β lam μ μ0 σ : ℝ) : EReal) := by sorry
end TwoEchelonCVRP.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.