Appendix G, Proof of Lemma 2, p. 42, (74) — if c_r + φ(SF1_r) > ub, route r is in no optimal solution of SF1
ProvedOnDemandDelivery.RouteElim.eq74Consider the routing subproblem SF1 of one period , with routes , costs , coverage coefficients and future-period coefficients . For a route , let SF1 be SF1 restricted to the routes covering only locations with , with right-hand sides reduced by 's own use, and let be its optimal cost ( if SF1 is infeasible).
Let be a real number that is at least the cost of every optimal solution of SF1. If
then for every optimal solution of SF1.
This is the exact elimination test behind Lemma 2: it is expensive because it needs the optimal cost of an integer program per route, and Lemma 2 replaces by an LP dual bound.
Formalization Note The sum is taken in the extended reals, so the test holds automatically when SF1 is infeasible. "An upper bound of problem SF1" is read in its weakest form: is at least the cost of every optimal solution (equivalently, whenever SF1 is feasible); no feasible solution of cost at most is required. The page writes for .
import Mathlib import Definitions.Def_OnDemandDelivery_RouteElim_Setting
namespace OnDemandDelivery.RouteElim
theorem eq74 {R I P : Type} [Fintype R] [Fintype I] [Fintype P]
(D : Data R I P) (hD : D.Standing)
(ub : ℝ) (hub : ∀ θ, D.SF1Optimal θ → D.cost θ ≤ ub)
(r : R) (h74 : (ub : EReal) < (D.c r : EReal) + D.phiSF1r r) :
∀ θ, D.SF1Optimal θ → θ r = 0 := by sorry
end OnDemandDelivery.RouteElim
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.