§2, p. 5 — the DWM (8)–(11) is (1)–(4) with x replaced by Qλ through (5)
ProvedRobustBCPCVRP.Formulation.dwm_substitutioncolumn-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
Let be weights on q-routes without 2-cycles in a CVRP instance with graph , demands , vehicles, capacity and lengths , and put , i.e. . Then
- satisfies the DWM constraints (8)–(11) if and only if satisfies (1)–(4);
- vanishes off and ;
- the DWM objective equals the edge objective:
This is the paper's passage from the Explicit Master to the more compact Dantzig–Wolfe Master: every occurrence of in (1)–(4) is replaced by its value given by (5).
Formalization Note In (8)–(10) the DWM is written with the paper's double sums , whereas (1)–(3) are written on the cut value of ; part 1 is the exchange of these sums.
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 dwm_substitution {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
(d : Fin (n + 1) → ℕ) (K C : ℕ) (ℓ : Sym2 (Fin (n + 1)) → ℝ)
(lam : List (Fin (n + 1)) →₀ ℝ) (hlam : IsColumns E d C lam) :
(IsDWMFeasible E d K C lam ↔
Deg1 (colSum lam) ∧ Deg2 K (colSum lam) ∧ Cap3 d C (colSum lam) ∧ Bnd4 E (colSum lam)) ∧
OnE E (colSum lam) ∧ Nonneg (colSum lam) ∧
dwmObjective E ℓ lam = ∑ e ∈ E, ℓ e * colSum lam e := 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, DWM (7)–(11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.