§2, p. 5 — a generic cut Σ aₑxₑ ≥ b becomes Σⱼ (Σₑ aₑqⱼᵉ) λⱼ ≥ b
ProvedRobustBCPCVRP.Formulation.generic_cut_translationcolumn-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Let be a graph, let be finitely supported weights on client lists (columns with edge incidences ), and let satisfy (5), for all . Then for every coefficient vector and every ,
Any valid inequality on the edge variables can therefore be added to the Dantzig–Wolfe Master without changing the structure of the pricing problem; this is what makes the method "robust".
Formalization Note The statement needs neither nonnegativity of nor that its support consists of q-routes; it holds for any weights satisfying (5).
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 generic_cut_translation {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
(x : Sym2 (Fin (n + 1)) → ℝ) (lam : List (Fin (n + 1)) →₀ ℝ)
(h5 : ∀ e ∈ E, colSum lam e = x e) (a : Sym2 (Fin (n + 1)) → ℝ) (b : ℝ) :
b ≤ ∑ e ∈ E, a e * x e ↔
b ≤ ∑ r ∈ lam.support, (∑ e ∈ E, a e * (inc r e : ℝ)) * lam 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. 5, §2, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.