§5.1 — LBW(M) is a lower bound on z(F(M))
ProvedTwoEchelonCVRP.Config.lbw_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). For every set of first-level routes visiting at least one satellite,
It is the bound used in condition (e) of Proposition 1 and in the order in which the exact method examines configurations.
Formalization Note The comparison is in EReal, so it is trivially true when is infeasible (). The paper takes the penalties producing LD1; any admissible ones are allowed here, and need not belong to .
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), and every
configuration `M` with `N_S(M)` nonempty, `LBW(M) ≤ z(F(M))`. -/
theorem lbw_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)
(M : Finset RS.FR) (hM : (NS RS M).Nonempty) :
((LBW RS β lam μ μ0 M hM : ℝ) : EReal) ≤ zFM RS M := 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 LBW(M)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.