Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 13 — with fixed pick-up times the MIO formulation (5)–(14) is integral

Proved
OnlineTaxiRouting.Integrality.theorem_1

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

extreme-pointsintegralitymixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1taxi-routing

Let C\mathcal CC be a finite set of customers and K\mathcal KK a finite set of taxis, with data tmin⁡,tmax⁡,tinit,T,Rt^{\min}, t^{\max}, t^{\mathrm{init}}, T, Rtmin,tmax,tinit,T,R as in the taxi routing model, and assume (standing assumption of §2.1) that the graph G\mathcal GG defined by the arc rule tcmin⁡+Tc,c′≤tc′max⁡t^{\min}_c + T_{c,c'} \le t^{\max}_{c'}tcmin​+Tc,c′​≤tc′max​ is acyclic. Suppose that every customer has a fixed pick-up time,

tcmin⁡=tcmax⁡=tc∗∀c∈C.t^{\min}_c = t^{\max}_c = t^*_c \qquad \forall c \in \mathcal C.tcmin​=tcmax​=tc∗​∀c∈C.

Then the mixed-integer formulation (5)–(14) is integral: every extreme point (x,y,p,t)(x, y, p, t)(x,y,p,t) of its LP relaxation — constraints (6)–(8), (12)–(14) and 0≤x,y,p≤10 \le x, y, p \le 10≤x,y,p≤1 — has

xc′,c, yk,c, pc∈{0,1}for all c′,c∈C, k∈K.x_{c',c},\ y_{k,c},\ p_c \in \{0, 1\} \quad \text{for all } c', c \in \mathcal C,\ k \in \mathcal K.xc′,c​, yk,c​, pc​∈{0,1}for all c′,c∈C, k∈K.

Integrality is a property of the feasible region, so the objective (5) plays no role in the statement. As a consequence, when pick-up times are fixed, the offline taxi routing problem can be solved by linear programming (for instance by the simplex method), and this underlies the paper's maxflow heuristic for problems with time windows.

Formalization Note Integrality concerns only the binary variables x,y,px, y, px,y,p; the times ttt are continuous and are equal to t∗t^*t∗ at every feasible point. The acyclicity hypothesis is the standing assumption of the paper's §2.1 and is kept, although the conclusion does not depend on it.

Preamble
import Mathlib
import Definitions.Def_OnlineTaxiRouting_Integrality_Setting
Formal statement
namespace OnlineTaxiRouting.Integrality

theorem theorem_1 {C K : Type*} [Fintype C] [Fintype K] (I : Instance C K)
    (hacyc : I.Acyclic) (hfix : ∀ c, I.tmin c = I.tmax c) :
    IsIntegral (relax I) := by sorry

end OnlineTaxiRouting.Integrality
Source
Bertsimas–Jaillet–Martin, accepted manuscript (March 2018), Theorem 1, p. 13
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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