Corollary 1 — routes with c̃_kl ≥ z(UB) − z(RF) are absent from every solution cheaper than z(UB)
ProvedTwoEchelonCVRP.LowerBound.corollary_1lower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reduced-costvehicle-routing
Consider a 2E-CVRP instance with positive demands and route families , . Let , , , let satisfy (12), and let
be the reduced cost of the second-level route . Let be a real number. Then every feasible solution of of cost smaller than uses no second-level route with ; that is, every route it uses satisfies
Reduced-cost fixing of this kind shrinks the route sets before the exact phase of the method.
Formalization Note The paper assumes is a valid upper bound and speaks of optimal solutions; neither is used, so the statement is given for any real and every feasible solution cheaper than it (a strengthening). The inequality is written with an addition because is an extended real.
Preamble
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF
Formal statement
namespace TwoEchelonCVRP.LowerBound
/-- Corollary 1 (p. 301): if `β` solves (12) and `μ ≤ 0`, `μ_0 ≤ 0`, then a feasible solution of F
of cost smaller than `zUB` uses no second-level route `l` with `c̃_l ≥ zUB − z(RF(β, λ, μ))`;
stated without subtraction as `c̃_l + z(RF) < zUB` for every used route. -/
theorem corollary_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)
(zUB : ℝ) (s : SolF RS) (hs : IsFeasibleF RS s) (hcost : costF RS s < zUB)
(l : RS.SR) (hl : s.x l = true) :
((reducedCost RS β lam μ μ0 l : ℝ) : EReal) + zRF RS β lam μ μ0 < ((zUB : ℝ) : 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, Corollary 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.