§3.2, pp. 12–13 — the relaxed network-flow system (6)–(11) on any arc subset has 0/1 extreme points
ProvedOnlineTaxiRouting.Integrality.flowRelax_extreme_zeroOneLet and be finite sets of customers and taxis, and let and be arbitrary sets of arcs. Let be the set of with
and for , for . Then every extreme point of has all coordinates , , in .
The paper observes that the constraints (6)–(11) describe a max-flow problem with integer bounds, so that the extreme points of the relaxation are integral and the simplex method returns an integral optimum; the proof of Theorem 1 ends by applying the same fact to the system in which some variables have been removed.
Formalization Note The page states the claim for the variables on the arcs of (and, in the proof of Theorem 1, for the system with variables removed). The statement here quantifies over every arc subset, which covers both cases (, everything is the system (6)–(11) as printed). No acyclicity is assumed: may contain cycles and loops .
import Mathlib import Definitions.Def_OnlineTaxiRouting_Integrality_Setting
namespace OnlineTaxiRouting.Integrality
theorem flowRelax_extreme_zeroOne {C K : Type*} [Fintype C] [Fintype K]
(A : C → C → Prop) (B : K → C → Prop) :
∀ w ∈ Set.extremePoints ℝ (flowRelax A B), IsZeroOneFlow w := by sorry
end OnlineTaxiRouting.Integrality
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.