Theorem 1 — z(RF(β, λ, μ)) is a lower bound on the cost of every feasible 2E-CVRP solution
ProvedTwoEchelonCVRP.LowerBound.theorem_1lagrangean-relaxationlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Consider a 2E-CVRP instance with positive demands and route families , . Let , for every and , and let satisfy the penalty system (12). Then for every feasible solution of formulation ,
In words, is a valid lower bound on the 2E-CVRP for any admissible choice of .
This is the first link in the chain that produces the paper's lower bound LD1; it also yields the reduced-cost elimination of Corollary 1.
Formalization Note The optimal value is an infimum in the extended reals ( if is infeasible), and "valid lower bound" is stated as the inequality against every feasible solution of , which is equivalent to .
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF
Formal statement
namespace TwoEchelonCVRP.LowerBound
/-- Theorem 1 (p. 301): for any solution `β` of (12) and penalties `λ ∈ ℝ^{N_C}`,
`μ ∈ ℝ_−^{N_S+1}`, `z(RF(β, λ, μ))` is at most the cost of every feasible solution of F. -/
theorem theorem_1 (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) :
zRF RS β lam μ μ0 ≤ ((costF RS s : ℝ) : EReal) := by sorry
end TwoEchelonCVRP.LowerBound
Source
Baldacci, Mingozzi, Roberti & Wolfler Calvo, An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem, Oper. Res. 61(2) (2013), p. 301, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.