Appendix G, Proof of Lemma 2, p. 42 — the restriction of a dual feasible solution of RF1 bounds φ(SF1_r) from below
ProvedOnDemandDelivery.RouteElim.rf1r_dual_boundlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routingweak-duality
In the routing subproblem of one period , let be a dual feasible solution of the LP relaxation RF1: , , , and for every route . Fix a route and let . Then:
- is a dual feasible solution of the restricted LP RF1 (75)–(79);
- its dual objective
is at most the cost of every feasible solution of RF1; 3. hence , the optimal cost of the restricted integer program.
This bound is the computable substitute for in the elimination test (74).
Formalization Note The page assumes dual optimal for RF1; the statement assumes only dual feasibility, which is all the argument needs, so it is a strengthening. The inequality is stated in the extended reals; it holds trivially when SF1 is infeasible. The double sum is written with .
Preamble
import Mathlib import Definitions.Def_OnDemandDelivery_RouteElim_Setting
Formal statement
namespace OnDemandDelivery.RouteElim
theorem rf1r_dual_bound {R I P : Type} [Fintype R] [Fintype I] [Fintype P]
(D : Data R I P) (hD : D.Standing)
(μ : P → ℝ) (μn : ℝ) (ν : I → ℝ) (hdual : D.DualFeasible μ μn ν) (r : R) :
D.RF1rDualFeasible r μ μn ν ∧
(∀ θ', D.RF1rFeasible r θ' → D.rf1rBound r μ μn ν ≤ D.cost θ') ∧
((D.rf1rBound r μ μn ν : ℝ) : EReal) ≤ D.phiSF1r 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, after (75)–(79)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.