Theorem 1, p. 13 — with fixed pick-up times the MIO formulation (5)–(14) is integral
ProvedOnlineTaxiRouting.Integrality.theorem_1Let be a finite set of customers and a finite set of taxis, with data as in the taxi routing model, and assume (standing assumption of §2.1) that the graph defined by the arc rule is acyclic. Suppose that every customer has a fixed pick-up time,
Then the mixed-integer formulation (5)–(14) is integral: every extreme point of its LP relaxation — constraints (6)–(8), (12)–(14) and — has
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 ; the times are continuous and are equal to 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.
import Mathlib import Definitions.Def_OnlineTaxiRouting_Integrality_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.