§2, p. 5 — the Explicit Master describes P₃ = P₁ ∩ P₂
ProvedRobustBCPCVRP.Formulation.P3_eq_P1_inter_P2column-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Let , demands , vehicles and capacity be a CVRP instance, and let , be the polytopes of the paper and the projection onto of the Explicit Master system (1)–(6), , , in which one vector of q-route weights serves both (5) and (6). Then
The paper's new formulation optimizes over the intersection of the cut polytope and the q-route polytope ; this statement identifies that intersection with the single lifted system the algorithm actually works with.
Formalization Note No hypothesis on the instance is needed. Membership is stated for every function on unordered pairs; each of requires to vanish off .
Preamble
import Mathlib import Definitions.Def_LysgaardCVRP_Shrink_cut import Definitions.Def_LysgaardCVRP_Shrink_roundedCapacityBound import Definitions.Def_RobustBCPCVRP_Formulation_Setting import Definitions.Def_RobustBCPCVRP_Formulation_Polytopes open LysgaardCVRP.Shrink
Formal statement
namespace RobustBCPCVRP.Formulation
theorem P3_eq_P1_inter_P2 {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
(d : Fin (n + 1) → ℕ) (K C : ℕ) (x : Sym2 (Fin (n + 1)) → ℝ) :
InP3 E d K C x ↔ InP1 E d K C x ∧ InP2 E d K C x := by sorry
end RobustBCPCVRP.Formulation
Source
Fukasawa, Longo, Lysgaard, Poggi de Aragão, Reis, Uchoa & Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program. (DOI 10.1007/s10107-005-0644-x); accepted manuscript, p. 5, §2, display of P₃ (left-hand side P₃ = P₁∩P₂)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.