§5.1 — LB_R is a lower bound on the second-level routing cost
ProvedTwoEchelonCVRP.Config.lbr_lower_boundlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1two-echelonvehicle-routing
Let be arbitrary, let for every satellite and , and let satisfy the penalty system (12). Assume there is at least one satellite. Then for every feasible solution of formulation ,
The paper states this for optimal solutions; it holds for every feasible one. It is the bound used in condition (d) of Proposition 1.
Formalization Note The paper takes the specific penalties that produce the bound LD1; here any penalties with , and (12) are allowed, a generalization.
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_Config_Bounds
Formal statement
namespace TwoEchelonCVRP.Config
/-- §5.1, p. 305: for penalties `μ ≤ 0`, `μ_0 ≤ 0`, any `λ` and any `β` satisfying (12), `LB_R` is
at most the second-level routing cost `∑_{k ∈ N_S} ∑_{l ∈ 𝓡_k} c_{kl} x_{kl}` of every feasible
solution of F. -/
theorem lbr_lower_bound (I : Instance) (RS : RouteSystem I) (hns : 0 < I.ns)
(β : 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) :
LBR hns β lam μ μ0 ≤ secondLevelCost RS s := by sorry
end TwoEchelonCVRP.Config
Source
Baldacci, Mingozzi, Roberti & Wolfler Calvo, An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem, Oper. Res. 61(2) (2013), p. 305, §5.1, the definition of LB_R
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.