Secs. 4–5, pp. 346 and 348 — with no negative marginal cost path, the restricted LP optimum solves the set covering LP, bounds every VRPTW solution, and is VRPTW-optimal when integral and exact
ProvedVRPTWColGen92.Bound.colgen_certificateThis is the optimality certificate of the column generation algorithm of Desrochers, Desrosiers and Solomon (1992) for the vehicle routing problem with time windows.
Fix a VRPTW instance. Let be a finite set of 2-cycle-free paths (the current columns), let be an optimal solution of the LP relaxation of the set covering type model (1)–(6) restricted to , and let be an optimal solution of the dual of that restricted LP. Suppose the pricing subproblem finds no negative marginal cost path: for every 2-cycle-free path of the instance,
Then:
- is an optimal solution of the LP relaxation of (1)–(6) over all 2-cycle-free paths;
- if moreover all arc costs are nonnegative, its value is at most the cost of every VRPTW solution;
- if moreover is integral and covers every customer exactly once ( for every customer ), then the columns with form a VRPTW solution whose cost equals and is at most the cost of every VRPTW solution: it is optimal for the VRPTW.
This is the statement behind the paper's "Otherwise, the current solution is optimal" (p. 346) and "If the solution is integer and each customer is covered exactly once, the solution is also optimal for the VRPTW" (p. 348).
Formalization Note. The LP relaxation keeps and relaxes to (root LP, no branching rows). Clauses 2 and 3 assume on arcs, the paper's "the cost is taken to be the distance between and ": without it the bound is false, because (6) forces while a VRPTW solution may have negative cost. Clause 1 needs no condition on the data.
import Mathlib import Definitions.Def_VRPTWColGen92_Bound_Network import Definitions.Def_VRPTWColGen92_Bound_CoveringLP
namespace VRPTWColGen92.Bound
theorem colgen_certificate {n : ℕ} (I : Instance n)
(R₀ : Finset (List (Fin (n + 1)))) (hR₀ : ∀ p ∈ R₀, IsPath3 I p)
(z : LPPoint n) (hz : LPOptimal I (↑R₀ : Set (List (Fin (n + 1)))) z)
(y : DualPoint n) (hy : DualOptimal I R₀ y)
(hprice : ∀ p, IsPath3 I p → 0 ≤ pathMarginal I y p) :
LPOptimal I {p | IsPath3 I p} z ∧
((∀ i j, I.arc i j → 0 ≤ I.c i j) →
(∀ S, IsVRPTWSolution I S → objective I z ≤ solCost I S) ∧
((∀ p, ∃ m : ℕ, z.x p = m) →
(∀ i : Fin (n + 1), i ≠ 0 → ∑ p ∈ z.x.support, (p.count i : ℝ) * z.x p = 1) →
IsVRPTWSolution I z.x.support ∧ solCost I z.x.support = objective I z ∧
∀ S, IsVRPTWSolution I S → solCost I z.x.support ≤ solCost I S)) := by sorry
end VRPTWColGen92.Bound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.