§3.2, after Theorem 3 — routes with c̃_kl ≥ z(UB) − z(RF-bar) are absent from every solution cheaper than z(UB)
ProvedTwoEchelonCVRP.LowerBound.rfbar_eliminationConsider a 2E-CVRP instance with positive demands and route families , . Let , , , let satisfy (12), and let be the reduced costs. 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 .
This is the route-elimination test the paper applies with the bound of , which is cheap to compute.
Formalization Note The paper speaks of optimal solutions of cost below a known upper bound; the statement is proved for every feasible solution of cost below , and is any real number (whether it is an upper bound is not used): both are strengthenings. The inequality is written with an addition instead of a subtraction because is an extended real.
import Mathlib import Definitions.Def_TwoEchelonCVRP_LowerBound_Model import Definitions.Def_TwoEchelonCVRP_LowerBound_RF import Definitions.Def_TwoEchelonCVRP_LowerBound_RFbar
namespace TwoEchelonCVRP.LowerBound
/-- §3.2, the sentence after Theorem 3 (p. 302): if `β` solves (12) and `μ ≤ 0`, `μ_0 ≤ 0`, a
feasible solution of F of cost smaller than `zUB` uses no second-level route `l` with
`c̃_l ≥ zUB − z(RF-bar(β, λ, μ))`; stated as `c̃_l + z(RF-bar) < zUB` for every used route. -/
theorem rfbar_elimination (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) + zRFbar RS β lam μ μ0
< ((zUB : ℝ) : EReal) := by sorry
end TwoEchelonCVRP.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.