Sec. 5, p. 348 — an integral LP solution covering each customer exactly once is a VRPTW solution of the same cost
ProvedVRPTWColGen92.Bound.exact_cover_is_vrptw_solutionLet be a feasible point of the LP relaxation of the set covering type model (1)–(6) over the paths of the second model (resource-feasible paths, customers possibly repeated). Suppose that is integral, for every column , and that every customer is covered exactly once:
Then the set of columns with is a VRPTW solution (a set of feasible routes, each visiting every customer at most once, covering every customer exactly once), and its cost equals the objective value .
In particular such a point uses only elementary routes, even though the LP allows columns with repeated customers.
Formalization Note. The statement is over second-model paths, which contain the 2-cycle-free paths, so it applies to the LP over 2-cycle-free paths as well.
import Mathlib import Definitions.Def_VRPTWColGen92_Bound_Network import Definitions.Def_VRPTWColGen92_Bound_CoveringLP
namespace VRPTWColGen92.Bound
theorem exact_cover_is_vrptw_solution {n : ℕ} (I : Instance n)
(z : LPPoint n) (hz : LPFeasible I {p | IsPath I p} z)
(hint : ∀ p, ∃ m : ℕ, z.x p = m)
(hexact : ∀ 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 := by sorry
end VRPTWColGen92.Bound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.