Appendix G, Proof of Lemma 2, p. 42, (80)–(81) — for a dual optimal solution of RF1, the bound test (80) is the reduced-cost test (81)
ProvedOnDemandDelivery.RouteElim.eq80_iff_eq81linear-programminglp-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduced-costvehicle-routing
In the routing subproblem of one period (with the standing assumptions ), suppose the LP relaxation RF1 attains its optimal cost , and let be a dual optimal solution of RF1. For every real and every route ,
holds if and only if
Here .
The equivalence turns the dual bound of RF1 into a test on the reduced cost of in RF1, which needs only one LP solve for all routes.
Formalization Note "The optimal cost " is the attained minimum of the cost over the RF1 feasible set, and "dual optimal" means maximal dual objective over the dual feasible set; the equality of with the dual objective of is not assumed. The double sum is written with .
Preamble
import Mathlib import Definitions.Def_OnDemandDelivery_RouteElim_Setting
Formal statement
namespace OnDemandDelivery.RouteElim
theorem eq80_iff_eq81 {R I P : Type} [Fintype R] [Fintype I] [Fintype P]
(D : Data R I P) (hD : D.Standing)
(φ : ℝ) (hφ : IsLeast (D.cost '' {θ | D.RF1Feasible θ}) φ)
(μ : P → ℝ) (μn : ℝ) (ν : I → ℝ) (hdual : D.DualOptimal μ μn ν)
(ub : ℝ) (r : R) :
ub < D.c r + D.rf1rBound r μ μn ν ↔ ub - φ < D.reducedCost μ μn ν r := by sorry
end OnDemandDelivery.RouteElim
Source
Liu, Luo, On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand, arXiv:2107.13058v3, p. 42, Appendix G, Proof of Lemma 2, (80)–(81)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.