Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2, p. 19 — a route whose reduced cost exceeds ub − φ(RF1) is in no optimal solution of SF1

Proved
OnDemandDelivery.RouteElim.lemma_2

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

integer-programminglp-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduced-costroute-eliminationvehicle-routing

Consider the single-period routing subproblem SF1 of the Benders decomposition of Liu and Luo: in period nnn, choose a set of routes from the finite route set Rn\mathcal R^nRn (binary θr\theta_rθr​) of minimum total cost ∑rθrcr\sum_r\theta_r c_r∑r​θr​cr​, so that every current location i∈Ini\in\mathcal I^ni∈In is served exactly once (∑rαi,rθr=1\sum_r\alpha_{i,r}\theta_r=1∑r​αi,r​θr​=1), at most Kˉ−ζnn\bar K-\zeta^n_nKˉ−ζnn​ routes are used, and in every future period n′n'n′ at most ∑k=0Kˉkzˉkn′\sum_{k=0}^{\bar K}k\bar z^{n'}_k∑k=0Kˉ​kzˉkn′​ chosen routes are still running. Here αi,r,βn′,r∈{0,1}\alpha_{i,r},\beta_{n',r}\in\{0,1\}αi,r​,βn′,r​∈{0,1}. Let RF1 be its LP relaxation (θ≥0\theta\ge0θ≥0, covering rows ≥1\ge 1≥1).

Let ububub be an upper bound of SF1 (at least the cost of every optimal solution), let ϕ(RF1)\phi(\mathrm{RF1})ϕ(RF1) be the optimal cost of RF1, let (μ,μn,ν)(\mu,\mu_n,\nu)(μ,μn​,ν) be a dual optimal solution of RF1 (dual variables μn′\mu_{n'}μn′​, μn\mu_nμn​, νi\nu_iνi​ of the rows (25), (19), (26)), and let r∈Rnr\in\mathcal R^nr∈Rn. If

cr−∑i∈Inαi,rνi−∑n′=n+1Nβn′,rμn′−μn>ub−ϕ(RF1),c_r-\sum_{i\in\mathcal I^n}\alpha_{i,r}\nu_i-\sum_{n'=n+1}^N\beta_{n',r}\mu_{n'}-\mu_n>ub-\phi(\mathrm{RF1}),cr​−i∈In∑​αi,r​νi​−n′=n+1∑N​βn′,r​μn′​−μn​>ub−ϕ(RF1),

then θr=0\theta_r=0θr​=0 in every optimal solution θ\thetaθ of SF1.

In words: once RF1 is solved, every route whose reduced cost exceeds the gap ub−ϕ(RF1)ub-\phi(\mathrm{RF1})ub−ϕ(RF1) can be discarded before SF1 is solved exactly. This is the pruning rule of the paper's route enumeration algorithm.

Formalization Note ϕ(RF1)\phi(\mathrm{RF1})ϕ(RF1) is the attained minimum of RF1 (an IsLeast hypothesis); "dual optimal" is maximality of the dual objective over the dual feasible set, with the standard sign convention μn′≤0\mu_{n'}\le0μn′​≤0, μn≤0\mu_n\le0μn​≤0, νi≥0\nu_i\ge0νi​≥0 (the paper does not print it). "An upper bound ububub of SF1" is read in its weakest form, ub≥ub\geub≥ the cost of every optimal solution. The standing assumptions also include zˉkn′∈{0,1}\bar z^{n'}_k\in\{0,1\}zˉkn′​∈{0,1} and ∑kzˉkn′=1\sum_k\bar z^{n'}_k=1∑k​zˉkn′​=1 ((17), (21)). Routes, locations and future periods are arbitrary finite types.

Preamble
import Mathlib
import Definitions.Def_OnDemandDelivery_RouteElim_Setting
Formal statement
namespace OnDemandDelivery.RouteElim

theorem lemma_2 {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)
    (φ : ℝ) (hφ : IsLeast (D.cost '' {θ | D.RF1Feasible θ}) φ)
    (μ : P → ℝ) (μn : ℝ) (ν : I → ℝ) (hdual : D.DualOptimal μ μn ν)
    (r : R) (h33 : ub - φ < D.reducedCost μ μn ν 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. 19, Lemma 2, (33)
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