While this submission is a draft, it cannot be used by other submissions.

Three-vertex examples separating path objectives

Lax330177.CostExamples · concepts/Lax330177/CostExamples.lean · lax-330177

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    7 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax330177.UniformCosts
    2
    3/-!
    4---
    5title: Three-vertex examples separating path objectives
    6type: definition
    7---
    8The chain 0 → 1 → 2 is available at times 0 through 3. An optional shortcut
    90 → 2 makes a triangle. Every traversal takes c units, where c is zero or one.
    10In the triangle compare the direct departures at 0 and 3 with the two-hop
    11journey departing at 0 and c. In the chain compare departures (0,3) with (0,c).
    12These 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-/
    18namespace Lax330177.CostExamples
    19open Lax330177.Representations Lax330177.Durations Lax330177.OptimalPaths
    20
    21abbrev 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
    26def 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
    33def 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
    49def 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
    67end Lax330177.CostExamples
    68
    69
    70

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…