§3.1, p. 7 — q-routes for the scaled demands ⌈dᵥ/g⌉ and capacity ⌊C/g⌋ are valid q-routes
ProvedRobustBCPCVRP.Formulation.scaling_validcolumn-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Let be a graph with integer demands and integer capacity , and let be an integer. Define the scaled demands and capacity
Every q-route without 2-cycles for the scaled data is a q-route without 2-cycles for the original data ; in particular its original load is at most .
This is the correctness of the scaling acceleration of the pricing: the dynamic program run on the scaled instance takes time proportional to instead of , and the columns it finds remain valid.
Formalization Note and are taken over the rationals (⌈(d v : ℚ) / g⌉₊, ⌊(C : ℚ) / g⌋₊).
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 scaling_valid {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
(d : Fin (n + 1) → ℕ) (C g : ℕ) (hg : 1 < g) (r : List (Fin (n + 1)))
(hr : IsQRoute E (fun v => ⌈(d v : ℚ) / g⌉₊) ⌊(C : ℚ) / g⌋₊ r) :
IsQRoute E d C r := 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. 7, §3.1, Heuristic Acceleration, scaling
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.