Sec. 4.1, p. 347 — the marginal cost of a route is the sum of the arc marginal costs (1 − π_c)c_ij − π_i
ProvedVRPTWColGen92.Bound.column_marginal_eq_arc_sumcolumn-generationlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduced-costvehicle-routing
Let be any values of the dual variables of the set covering LP, and let be given by a customer list that does not contain the depot. Then the marginal cost of the column ,
equals the sum of the arc marginal costs along :
This is what lets the pricing subproblem be solved as a shortest path problem with arc costs .
Formalization Note. The identity is algebraic; it needs only that the depot appears at the two ends of the node sequence and nowhere else, so that each customer visit contributes its dual once and the depot contributes once. No arc, window or capacity condition is assumed.
Preamble
import Mathlib import Definitions.Def_VRPTWColGen92_Bound_Network import Definitions.Def_VRPTWColGen92_Bound_CoveringLP
Formal statement
namespace VRPTWColGen92.Bound
theorem column_marginal_eq_arc_sum {n : ℕ} (I : Instance n) (y : DualPoint n)
(p : List (Fin (n + 1))) (hp : (0 : Fin (n + 1)) ∉ p) :
columnMarginal I y p = pathMarginal I y p := by sorry
end VRPTWColGen92.Bound
Source
Desrochers, Desrosiers & Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Oper. Res. 40 (1992), p. 347, Sec. 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.