§3.2, proof of Theorem 1, p. 13 — with fixed times the relaxation is the flow system (6)–(11) without the forced-zero arcs
ProvedOnlineTaxiRouting.Integrality.relax_eq_flow_of_fixedConsider a taxi routing instance with fixed pick-up times for all customers . Let
Then a point lies in the LP relaxation of (5)–(14) if and only if and lies in the relaxed network-flow system (6)–(11) on the arc subset , i.e. satisfies (6)–(8), , for and for .
In words: with fixed times, (13) forces exactly when and is otherwise inactive; the same reasoning applied to (14) forces exactly when . This is the second step of the proof of Theorem 1: the feasible region in is that of the network-flow constraints with some variables removed.
Formalization Note The standing acyclicity assumption of §2.1 is not needed and is omitted. The page states the taxi-arc case only as "the same reasoning applies to Constraint (14)"; the set above is that reasoning written out.
import Mathlib import Definitions.Def_OnlineTaxiRouting_Integrality_Setting
namespace OnlineTaxiRouting.Integrality
theorem relax_eq_flow_of_fixed {C K : Type*} [Fintype C] [Fintype K]
(I : Instance C K) (hfix : ∀ c, I.tmin c = I.tmax c) :
relax I = {v | (v.1, v.2.1, v.2.2.1) ∈
flowRelax (fun c' c => I.T c' c ≤ I.tmin c - I.tmin c')
(fun k c => I.tinit k + I.Tk k c ≤ I.tmin c) ∧
v.2.2.2 = I.tmin} := by sorry
end OnlineTaxiRouting.Integrality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.