Theorem 4 — the marginal costs (24) over non-elementary routes solve the penalty system (12)
ProvedTwoEchelonCVRP.LowerBound.theorem_4lagrangean-relaxationng-routesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Consider a 2E-CVRP instance with positive demands and route families , , and let be enlarged families of not necessarily elementary routes. For any penalties , , , the vector given by
is a feasible solution of the penalty system (12):
This is how the paper's bounding procedure produces, at every step, a to which Theorems 1 and 3 apply.
Formalization Note The paper takes ; the statement holds for all real penalties, so the sign conditions are not assumed. is when is empty, a value that does not enter (12).
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF import Definitions.Def_TwoEchelonCVRP_LowerBound_ExtRoutes
Formal statement
namespace TwoEchelonCVRP.LowerBound
/-- Theorem 4 (p. 302): for any enlarged family `𝓡̂_k ⊇ 𝓡_k` of not necessarily elementary routes,
the marginal costs `β_{ik}` of (24) solve the penalty system (12). -/
theorem theorem_4 (I : Instance) (RS : RouteSystem I) (E : ExtRoutes RS)
(lam : Fin I.nc → ℝ) (μ : Fin I.ns → ℝ) (μ0 : ℝ) :
SatisfiesPenalty RS (E.beta24 lam μ μ0) lam μ μ0 := 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. 302, Theorem 4, Eq. (24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.