§3.2, proof of Theorem 1, display (15), p. 13 — with fixed windows (12) forces t = t*, and (13) becomes (15)
ProvedOnlineTaxiRouting.Integrality.eq15_of_fixedbig-mmixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1taxi-routing
Consider a taxi routing instance in which every customer has a fixed pick-up time, for all . Then for every point :
- the window constraint (12), for all , holds if and only if ;
- if , then for every pair of customers the time constraint (13) holds if and only if
This is the first step of the proof of Theorem 1: once the pick-up times are fixed, the Big-M constraint (13) only constrains the single variable .
Formalization Note The standing acyclicity assumption of §2.1 is not needed and is omitted, which makes the statement stronger.
Preamble
import Mathlib import Definitions.Def_OnlineTaxiRouting_Integrality_Setting
Formal statement
namespace OnlineTaxiRouting.Integrality
theorem eq15_of_fixed {C K : Type*} (I : Instance C K)
(hfix : ∀ c, I.tmin c = I.tmax c) (v : Var C K) :
((∀ c, I.tmin c ≤ v.2.2.2 c ∧ v.2.2.2 c ≤ I.tmax c) ↔ v.2.2.2 = I.tmin) ∧
(v.2.2.2 = I.tmin → ∀ c c',
((I.tmin c - I.tmax c') + (I.T c' c - (I.tmin c - I.tmax c')) * v.1 c' c
≤ v.2.2.2 c - v.2.2.2 c' ↔
(I.T c' c - (I.tmin c - I.tmin c')) * v.1 c' c ≤ 0)) := by sorry
end OnlineTaxiRouting.Integrality
Source
Bertsimas–Jaillet–Martin, accepted manuscript (March 2018), §3.2, proof of Theorem 1, display (15), p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.