Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix G, Proof of Lemma 2, p. 42, (74) — if c_r + φ(SF1_r) > ub, route r is in no optimal solution of SF1

Proved
OnDemandDelivery.RouteElim.eq74

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1route-eliminationvehicle-routing

Consider the routing subproblem SF1 of one period nnn, with routes Rn\mathcal R^nRn, costs crc_rcr​, coverage coefficients αi,r∈{0,1}\alpha_{i,r}\in\{0,1\}αi,r​∈{0,1} and future-period coefficients βn′,r∈{0,1}\beta_{n',r}\in\{0,1\}βn′,r​∈{0,1}. For a route rrr, let SF1r_rr​ be SF1 restricted to the routes covering only locations iii with αi,r=0\alpha_{i,r}=0αi,r​=0, with right-hand sides reduced by rrr's own use, and let ϕ(SF1r)∈R∪{+∞}\phi(\mathrm{SF1}_r)\in\mathbb R\cup\{+\infty\}ϕ(SF1r​)∈R∪{+∞} be its optimal cost (+∞+\infty+∞ if SF1r_rr​ is infeasible).

Let ububub be a real number that is at least the cost of every optimal solution of SF1. If

cr+ϕ(SF1r)>ub,c_r+\phi(\mathrm{SF1}_r)>ub,cr​+ϕ(SF1r​)>ub,

then θr=0\theta_r=0θr​=0 for every optimal solution θ\thetaθ 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 ϕ(SF1r)\phi(\mathrm{SF1}_r)ϕ(SF1r​) by an LP dual bound.

Formalization Note The sum cr+ϕ(SF1r)c_r+\phi(\mathrm{SF1}_r)cr​+ϕ(SF1r​) is taken in the extended reals, so the test holds automatically when SF1r_rr​ is infeasible. "An upper bound ububub of problem SF1" is read in its weakest form: ububub is at least the cost of every optimal solution (equivalently, ub≥ϕ(SF1)ub\ge\phi(\mathrm{SF1})ub≥ϕ(SF1) whenever SF1 is feasible); no feasible solution of cost at most ububub is required. The page writes Rn\mathcal R_nRn​ for Rn\mathcal R^nRn.

Preamble
import Mathlib
import Definitions.Def_OnDemandDelivery_RouteElim_Setting
Formal statement
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
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, (74)
Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me