Three-vertex examples separating path objectives
Lax330177.CostExamples · concepts/Lax330177/CostExamples.lean · lax-330177
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The chain 0 → 1 → 2 is available at times 0 through 3. An optional shortcut 0 → 2 makes a triangle. Every traversal takes c units, where c is zero or one. In the triangle compare the direct departures at 0 and 3 with the two-hop journey departing at 0 and c. In the chain compare departures (0,3) with (0,c). These witnesses distinguish optimality predicates, allowing ties.
- Early and late direct paths. In the triangle, direct departures at 0 and 3 both minimize hops, elapsed time and waiting for either traversal cost. Of these two paths, only the early one is foremost and only the late one is latest-departing.
- A shortest path can wait longer. On the chain without the shortcut, departures at 0 and 3 give a shortest path for either traversal cost. Another feasible path arrives in less elapsed time and has less total waiting.
- A detour with no waiting. In the triangle, the two-hop path departing at 0 and c minimizes waiting for either traversal cost and uses more hops than the shortcut. It is fastest exactly when c is zero.
Concept map
Lean source view on GitHub
| 1 | import Lax330177.UniformCosts |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Three-vertex examples separating path objectives |
| 6 | type: definition |
| 7 | --- |
| 8 | The chain 0 → 1 → 2 is available at times 0 through 3. An optional shortcut |
| 9 | 0 → 2 makes a triangle. Every traversal takes c units, where c is zero or one. |
| 10 | In the triangle compare the direct departures at 0 and 3 with the two-hop |
| 11 | journey departing at 0 and c. In the chain compare departures (0,3) with (0,c). |
| 12 | These witnesses distinguish optimality predicates, allowing ties. |
| 13 | |
| 14 | - [Early and late direct paths.](Lax330177Proofs.CostExamples.direct_choices.html) In the triangle, direct departures at 0 and 3 both minimize hops, elapsed time and waiting for either traversal cost. Of these two paths, only the early one is foremost and only the late one is latest-departing. |
| 15 | - [A shortest path can wait longer.](Lax330177Proofs.CostExamples.slow_shortest.html) On the chain without the shortcut, departures at 0 and 3 give a shortest path for either traversal cost. Another feasible path arrives in less elapsed time and has less total waiting. |
| 16 | - [A detour with no waiting.](Lax330177Proofs.CostExamples.no_wait_detour.html) In the triangle, the two-hop path departing at 0 and c minimizes waiting for either traversal cost and uses more hops than the shortcut. It is fastest exactly when c is zero. |
| 17 | -/ |
| 18 | namespace Lax330177.CostExamples |
| 19 | open Lax330177.Representations Lax330177.Durations Lax330177.OptimalPaths |
| 20 | |
| 21 | abbrev network (shortcut : Bool) : Graph 3 where |
| 22 | lifetime := 4 |
| 23 | edge _ u v := u.val + 1 = v.val ∨ (shortcut = true ∧ u = 0 ∧ v = 2) |
| 24 | loopless := by intro t u; fin_cases u <;> simp |
| 25 | |
| 26 | def query (shortcut : Bool) (c : Fin 2) : Query (network shortcut) where |
| 27 | source := 0 |
| 28 | target := 2 |
| 29 | release := 0 |
| 30 | deadline := 3+c.val |
| 31 | transit _ _ _ := c.val |
| 32 | |
| 33 | def direct (late : Bool) (c : Fin 2) : Candidate (query true c) where |
| 34 | hops := 1 |
| 35 | vertex := ![0,2] |
| 36 | time := fun _ => if late then 3 else 0 |
| 37 | departure := if late then 3 else 0 |
| 38 | arrival := (if late then 3 else 0) + c.val |
| 39 | feasible := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 40 | starts := rfl |
| 41 | ends := rfl |
| 42 | released := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 43 | inOrder := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 44 | onTime := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 45 | first := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 46 | last := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 47 | instantaneous := by cases late <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 48 | |
| 49 | def via (shortcut slow : Bool) (c : Fin 2) : Candidate (query shortcut c) where |
| 50 | hops := 2 |
| 51 | vertex := id |
| 52 | time := ![0, if slow then 3 else ⟨c.val, by change c.val < 4; omega⟩] |
| 53 | departure := 0 |
| 54 | arrival := (if slow then 3 else c.val) + c.val |
| 55 | feasible := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 56 | starts := rfl |
| 57 | ends := rfl |
| 58 | released := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 59 | inOrder := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 60 | onTime := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 61 | first := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 62 | last := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 63 | instantaneous := by cases shortcut <;> cases slow <;> fin_cases c <;> dsimp [DurationPath, Feasible, query, network] <;> decide |
| 64 | |
| 65 | |
| 66 | |
| 67 | end Lax330177.CostExamples |
| 68 | |
| 69 | |
| 70 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments