Files

900 lines
39 KiB
Lean4
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.CountBridge
import FormalConflictRange.DiffFeasible
/-!
# Deciding the finite count relaxation
We translate the finite count feasibility of `CountBridge.lean` into integer
difference constraints on cumulative counts and decide the latter by variable
elimination (`DiffFeasible.lean`).
-/
namespace FormalConflictRange
/-- Prefix sum of the first `i` interval counts. -/
def pref (counts : List ℕ) (i : ℕ) : ℕ := (counts.take i).sum
/-- Cumulative counts extracted from a count assignment, with the last variable
standing for the total count including the unbounded final interval. -/
def countsToX (n : ℕ) (counts : List ℕ) (topCount : ℕ) (i : ℕ) : ℤ :=
if i = n + 1 then (counts.sum + topCount : ℕ) else (pref counts i : ℕ)
/-- The cumulative lookup in `countAtWith` is the prefix sum. -/
theorem countAtWith_eq_pref (base : ℕ) {bounds : List Key} {counts : List ℕ}
(hlen : counts.length = bounds.length) {k : Key} (hk : k ∈ bounds) :
countAtWith base bounds counts k =
base + pref counts (bounds.idxOf k + 1) := by
induction bounds generalizing base counts with
| nil => simp at hk
| cons b bs ih =>
cases counts with
| nil => simp at hlen
| cons d ds =>
have hlen' : ds.length = bs.length := by simpa using hlen
by_cases hkb : k = b
· subst k
simp [countAtWith, pref, List.idxOf_cons_self]
· have hkbs : k ∈ bs := by
rcases List.mem_cons.mp hk with rfl | hkbs
· exact absurd rfl hkb
· exact hkbs
rw [List.idxOf_cons_ne bs (fun h => hkb h.symm)]
simp only [countAtWith, ite_eq_right hkb]
rw [ih (base := base + d) hlen' hkbs]
simp [pref, List.take_succ_cons, List.sum_cons]
omega
/-- The variable index of an endpoint in the cumulative count vector. -/
def endpointIndex (bounds : List Key) : WithTop Key → ℕ
| some k => if k = ([] : Key) then 0 else bounds.idxOf k + 1
| none => bounds.length + 1
/-- Capacity and nonnegativity edges for consecutive interval counts. -/
def capEdgesAux (start : Key) (bounds : List Key) (i : ℕ) : List DEdge :=
match bounds with
| [] => []
| b :: bs =>
[⟨i + 1, i, 0⟩] ++
(if _h : intervalCard (start : WithTop Key) (b : WithTop Key) = ⊤ then []
else [⟨i, i + 1, ((intervalCard (start : WithTop Key) (b : WithTop Key)).toNat : ℤ)⟩]) ++
capEdgesAux b bs (i + 1)
/-- The full capacity/order system, including the nonnegativity of the final
unbounded interval count. -/
def capEdges (bounds : List Key) : List DEdge :=
capEdgesAux ([] : Key) bounds 0 ++
[⟨bounds.length + 1, bounds.length, 0⟩]
/-- The coefficient of the toggle shift on an endpoint. -/
def toggleCoeff (stored : Bool) (k : Key) (e : WithTop Key) : ℤ :=
if (k : WithTop Key) < e then (if stored then (-1 : ℤ) else 1) else 0
/-- An edge for a constraint `lo hi bound`. -/
def constraintEdge (bounds : List Key) (lo hi : WithTop Key) (w : ℤ) : DEdge :=
⟨endpointIndex bounds lo, endpointIndex bounds hi, w⟩
/-- The edges encoding a whole constraint system. -/
def constraintEdges (bounds : List Key) (S : ConstraintSystem) : List DEdge :=
S.map fun c => constraintEdge bounds c.lo c.hi c.bound
/-- The edges encoding the toggled failures of a chosen list of constraints. -/
def badEdges (bounds : List Key) (k : Key) (stored : Bool)
(bad : List Constraint) : List DEdge :=
bad.map fun c =>
constraintEdge bounds c.hi c.lo
(toggleCoeff stored k c.hi - toggleCoeff stored k c.lo - c.bound - 1)
/-- The two edges forcing the toggle indicator to be `1` (stored) or `0` (absent). -/
def branchEqEdges (bounds : List Key) (k : Key) (stored : Bool) : List DEdge :=
let i := endpointIndex bounds (k : WithTop Key)
let j := endpointIndex bounds ((keyAfter k : Key) : WithTop Key)
if stored then [⟨i, j, 1⟩, ⟨j, i, -1⟩] else [⟨i, j, 0⟩, ⟨j, i, 0⟩]
/-- The complete difference system for one branch of the finite count relaxation. -/
def countDiffEdges (bounds : List Key) (k : Key) (stored : Bool)
(S : ConstraintSystem) (bad : List Constraint) : List DEdge :=
capEdges bounds ++ constraintEdges bounds S ++ badEdges bounds k stored bad ++
branchEqEdges bounds k stored
/-- The finite-count feasibility predicate for one toggle-indicator branch. -/
def CountFeasibleBranch (bounds : List Key) (k : Key) (stored : Bool)
(S : ConstraintSystem) (bad : List Constraint) : Prop :=
∃ counts : List ℕ, ∃ topCount : ℕ,
CountsFit ([] : Key) bounds counts ∧
SystemHoldsWithCounts S bounds counts topCount ∧
evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = (if stored then 1 else 0) ∧
∀ c ∈ bad, c.bound <
evalCountToggled bounds counts topCount k c.hi -
evalCountToggled bounds counts topCount k c.lo
/-- `x` has prefix sums given by `counts`, starting at index `i`. -/
def PrefixCum (x : ℕ → ℤ) (i : ℕ) (counts : List ℕ) : Prop :=
∀ k ≤ counts.length, x (i + k) - x i = (pref counts k : ℤ)
theorem pref_succ (counts : List ℕ) {i : ℕ} (hi : i < counts.length) :
pref counts (i + 1) = pref counts i + counts[i] := by
unfold pref
rw [List.sum_take_succ counts i hi]
theorem pref_zero (counts : List ℕ) : pref counts 0 = 0 := by simp [pref]
theorem pref_cons_succ (d : ℕ) (ds : List ℕ) (k : ℕ) :
pref (d :: ds) (k + 1) = d + pref ds k := by
simp [pref, List.take_succ_cons, List.sum_cons]
theorem prefixCum_cons_head {x : ℕ → ℤ} {i d} {ds : List ℕ}
(h : PrefixCum x i (d :: ds)) :
x (i + 1) - x i = (d : ℤ) := by
have := h 1 (by simp)
simpa [pref_cons_succ, pref_zero] using this
theorem prefixCum_tail {x : ℕ → ℤ} {i d} {ds : List ℕ}
(h : PrefixCum x i (d :: ds)) : PrefixCum x (i + 1) ds := by
intro k hk
have h1 := h (k + 1) (by simp [Nat.succ_le_succ_iff.mpr hk])
have h0 := h 1 (by simp)
have : x (i + (k + 1)) - x i - (x (i + 1) - x i) =
(pref (d :: ds) (k + 1) : ℤ) - (pref (d :: ds) 1 : ℤ) := by
rw [h1, h0]
rw [pref_cons_succ, pref_cons_succ, pref_zero] at this
have harg : i + (k + 1) = i + 1 + k := by omega
rw [harg] at this
have hpref : ((d + pref ds k : ℕ) : ℤ) - ((d + 0 : ℕ) : ℤ) = (pref ds k : ℤ) := by
push_cast
ring
linarith
theorem prefixCum_countsToX (n : ℕ) (counts : List ℕ) (topCount : ℕ)
(hlen : counts.length = n) : PrefixCum (countsToX n counts topCount) 0 counts := by
intro k hk
have hk' : k ≤ n := by omega
have hne : k ≠ n + 1 := by omega
simp [countsToX, hne, pref_zero]
theorem length_eq_of_countsFit {start : Key} {bounds : List Key} {counts : List ℕ}
(h : CountsFit start bounds counts) : counts.length = bounds.length := by
induction bounds generalizing start counts with
| nil =>
cases counts with
| nil => rfl
| cons d ds => simp [CountsFit] at h
| cons b bs ih =>
cases counts with
| nil => simp [CountsFit] at h
| cons d ds => simp only [CountsFit] at h; exact congrArg Nat.succ (ih h.2.2)
/-- Capacity edges hold when the prefix-cumulative assignment comes from a
capacity-fitting count list. -/
theorem capEdgesAux_holds_of_countsFit {start : Key} {bounds : List Key}
{counts : List ℕ} {x : ℕ → ℤ} {i : ℕ}
(hfit : CountsFit start bounds counts) (hlen : counts.length = bounds.length)
(hx : PrefixCum x i counts) :
HoldsAll x (capEdgesAux start bounds i) := by
induction bounds generalizing start counts i with
| nil =>
have : counts = [] := by
cases counts with
| nil => rfl
| cons d ds => simp at hlen
subst this
simp [capEdgesAux, HoldsAll]
| cons b bs ih =>
cases counts with
| nil => simp [CountsFit] at hfit
| cons d ds =>
rcases hfit with ⟨hstartb, hcap, hfitTail⟩
have hlen' : ds.length = bs.length := by simpa using hlen
have hhead := prefixCum_cons_head hx
have htail := prefixCum_tail hx
have hnonneg : x i - x (i + 1) ≤ 0 := by linarith [hhead]
have hcapEdge : HoldsAll x
(if h : intervalCard (start : WithTop Key) (b : WithTop Key) = ⊤ then []
else [⟨i, i + 1, ((intervalCard (start : WithTop Key) (b : WithTop Key)).toNat :
ℤ)⟩]) := by
by_cases htop : intervalCard (start : WithTop Key) (b : WithTop Key) = ⊤
· simp [htop, HoldsAll]
· intro e he
simp only [htop, ↓reduceDIte, List.mem_singleton] at he
subst he
simp only [DEdge.Holds]
have hcast : (d : ℕ∞) ≤ intervalCard (start : WithTop Key) (b : WithTop Key) := hcap
have hnat : d ≤ (intervalCard (start : WithTop Key) (b : WithTop Key)).toNat := by
have := ENat.natCast_toNat_eq_self.mpr htop
rw [← this] at hcast
exact_mod_cast hcast
rw [hhead]
exact_mod_cast hnat
intro e he
-- `capEdgesAux start (b :: bs) i` is `([nonneg] ++ caps) ++ tail`
rcases List.mem_append.mp he with hheadList | htailList
· rcases List.mem_append.mp hheadList with hnon | hcapMem
· simp only [List.mem_singleton] at hnon
rw [hnon]
simpa [DEdge.Holds] using hnonneg
· exact hcapEdge e hcapMem
· exact ih hfitTail hlen' htail e htailList
/-- Conversely, capacity edges produce a capacity-fitting count list. -/
theorem countsFit_of_capEdgesAux {start : Key} {bounds : List Key}
{counts : List ℕ} {x : ℕ → ℤ} {i : ℕ}
(hle : BoundsLe start bounds) (hlen : counts.length = bounds.length)
(hx : PrefixCum x i counts) (h : HoldsAll x (capEdgesAux start bounds i)) :
CountsFit start bounds counts := by
induction bounds generalizing start counts i with
| nil =>
cases counts with
| nil => simp [CountsFit]
| cons d ds => simp at hlen
| cons b bs ih =>
cases counts with
| nil => simp at hlen
| cons d ds =>
rcases hle with ⟨hstartb, hleTail⟩
have hlen' : ds.length = bs.length := by simpa using hlen
have hhead := prefixCum_cons_head hx
have htail := prefixCum_tail hx
have hnonnegEdge : (⟨i + 1, i, 0⟩ : DEdge) ∈ capEdgesAux start (b :: bs) i := by
simp [capEdgesAux]
have hnonneg := h _ hnonnegEdge
simp only [DEdge.Holds] at hnonneg
have hd_nonneg : (0 : ℤ) ≤ (d : ℤ) := by linarith [hhead]
have hcap : (d : ℕ∞) ≤ intervalCard (start : WithTop Key) (b : WithTop Key) := by
by_cases htop : intervalCard (start : WithTop Key) (b : WithTop Key) = ⊤
· rw [htop]; exact le_top
· have hmem : (⟨i, i + 1,
((intervalCard (start : WithTop Key) (b : WithTop Key)).toNat : ℤ)⟩ : DEdge) ∈
capEdgesAux start (b :: bs) i := by
simp [capEdgesAux, htop]
have hcapInt := h _ hmem
simp only [DEdge.Holds] at hcapInt
rw [hhead] at hcapInt
have hdNat : d ≤ (intervalCard (start : WithTop Key) (b : WithTop Key)).toNat := by
exact_mod_cast hcapInt
have hcast := ENat.natCast_toNat_eq_self.mpr htop
rw [← hcast]
exact_mod_cast hdNat
refine ⟨hstartb, hcap, ?_⟩
apply ih hleTail hlen' htail
intro e he
exact h e (List.mem_append.mpr (Or.inr he))
/-- Evaluation of the count environment is the corresponding cumulative variable. -/
theorem evalCount_eq_countsToX {bounds : List Key} {counts : List ℕ}
{topCount : ℕ} (hlen : counts.length = bounds.length)
(_hnoBot : ([] : Key) ∉ bounds) {e : WithTop Key}
(he : EndpointCovered e bounds) :
evalCount bounds counts topCount e =
countsToX bounds.length counts topCount (endpointIndex bounds e) := by
rcases he with rfl | rfl | ⟨k, hk, rfl⟩
· -- bottom
simp [evalCount, countsToX, endpointIndex, pref]
· -- top
simp [evalCount, countsToX, endpointIndex]
· -- finite nonempty endpoint
by_cases hkbot : k = ([] : Key)
· simp [evalCount, countsToX, endpointIndex, hkbot, pref]
· have hidxlt : bounds.idxOf k < bounds.length :=
List.idxOf_lt_length_iff.mpr hk
have hlen' : counts.length = bounds.length := hlen
have hlook := countAtWith_eq_pref (base := 0) hlen' hk
have hne : bounds.idxOf k ≠ bounds.length := by omega
have hnot : k ≠ ([] : Key) := hkbot
simp [evalCount, countsToX, endpointIndex, hkbot, hne, hlook]
/-- The toggled count environment is the untoggled one plus the toggle coefficient,
once the toggle indicator is pinned to the branch value. -/
theorem evalCountToggled_eq_add_toggleCoeff {bounds : List Key} {counts : List ℕ}
{topCount : ℕ} {k : Key} {stored : Bool}
(hxd : evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = (if stored then 1 else 0))
(e : WithTop Key) :
evalCountToggled bounds counts topCount k e =
evalCount bounds counts topCount e + toggleCoeff stored k e := by
unfold evalCountToggled toggleShift toggleCoeff
by_cases hlt : (k : WithTop Key) < e
· cases stored <;> simp [hlt, hxd]
· simp [hlt]
/-- The constraint edges hold exactly when the count environment satisfies the
constraint system. -/
theorem constraintEdges_holds_iff {bounds : List Key} {counts : List ℕ}
{topCount : ℕ} {S : ConstraintSystem}
(_hlen : counts.length = bounds.length) {x : ℕ → ℤ}
(hx : ∀ e : WithTop Key, EndpointCovered e bounds → x (endpointIndex bounds e) =
evalCount bounds counts topCount e)
(hcover : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds) :
HoldsAll x (constraintEdges bounds S) ↔ SystemHoldsWithCounts S bounds counts topCount := by
unfold constraintEdges SystemHoldsWithCounts
constructor
· intro h c hc
have hlo := hcover c hc
have hedge := h (constraintEdge bounds c.lo c.hi c.bound) (List.mem_map.mpr ⟨c, hc, rfl⟩)
simp only [constraintEdge, DEdge.Holds] at hedge
rw [hx c.hi hlo.2, hx c.lo hlo.1] at hedge
exact hedge
· intro h e he
rw [List.mem_map] at he
obtain ⟨c, hc, rfl⟩ := he
have hlo := hcover c hc
simp only [constraintEdge, DEdge.Holds]
rw [hx c.hi hlo.2, hx c.lo hlo.1]
exact h c hc
/-- The bad edges hold exactly when every chosen constraint fails after the
toggle. -/
theorem badEdges_holds_iff {bounds : List Key} {counts : List ℕ}
{topCount : ℕ} {k : Key} {stored : Bool} {bad : List Constraint}
{x : ℕ → ℤ}
(hxd : evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = (if stored then 1 else 0))
(hx : ∀ e : WithTop Key, EndpointCovered e bounds → x (endpointIndex bounds e) =
evalCount bounds counts topCount e)
(hcover : ∀ c ∈ bad, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds) :
HoldsAll x (badEdges bounds k stored bad) ↔
∀ c ∈ bad, c.bound <
evalCountToggled bounds counts topCount k c.hi -
evalCountToggled bounds counts topCount k c.lo := by
unfold badEdges
constructor
· intro h c hc
have hlo := hcover c hc
have hedge := h (constraintEdge bounds c.hi c.lo
(toggleCoeff stored k c.hi - toggleCoeff stored k c.lo - c.bound - 1))
(List.mem_map.mpr ⟨c, hc, rfl⟩)
simp only [constraintEdge, DEdge.Holds] at hedge
rw [hx c.hi hlo.2, hx c.lo hlo.1] at hedge
rw [evalCountToggled_eq_add_toggleCoeff hxd c.hi,
evalCountToggled_eq_add_toggleCoeff hxd c.lo]
omega
· intro h e he
rw [List.mem_map] at he
obtain ⟨c, hc, rfl⟩ := he
have hlo := hcover c hc
have hbad := h c hc
rw [evalCountToggled_eq_add_toggleCoeff hxd c.hi,
evalCountToggled_eq_add_toggleCoeff hxd c.lo] at hbad
simp only [constraintEdge, DEdge.Holds]
rw [hx c.hi hlo.2, hx c.lo hlo.1]
omega
/-- The interval counts read off from a cumulative assignment. -/
def diffCounts (x : ℕ → ℤ) : ℕ → List ℕ
| 0 => []
| n + 1 => diffCounts x n ++ [(x (n + 1) - x n).toNat]
theorem diffCounts_length (x : ℕ → ℤ) (n : ℕ) : (diffCounts x n).length = n := by
induction n with
| zero => rfl
| succ n ih => simp [diffCounts, ih]
theorem pref_append_singleton_le {l : List ℕ} {d k : ℕ} (hk : k ≤ l.length) :
pref (l ++ [d]) k = pref l k := by
unfold pref
rw [List.take_append_of_le_length hk]
theorem pref_append_singleton_self (l : List ℕ) (d : ℕ) :
pref (l ++ [d]) (l.length + 1) = pref l l.length + d := by
unfold pref
have hlen : l.length + 1 = (l ++ [d]).length := by simp
rw [hlen, List.take_length]
simp
theorem pref_length (l : List ℕ) : pref l l.length = l.sum := by
simp [pref]
theorem pref_eq_sum_of_length_le {l : List ℕ} {n : ℕ} (h : l.length ≤ n) :
pref l n = l.sum := by
unfold pref
rw [List.take_of_length_le h]
/-- Differences read off from `x` telescope back to `x`. -/
theorem prefixCum_diffCounts {x : ℕ → ℤ} (h0 : x 0 = 0) (n : ℕ)
(hnonneg : ∀ i < n, 0 ≤ x (i + 1) - x i) :
PrefixCum x 0 (diffCounts x n) := by
induction n with
| zero =>
intro k hk
have hk0 : k = 0 := by simpa [diffCounts] using hk
subst k
simp [ h0, pref]
| succ n ih =>
intro k hk
have hk' : k ≤ n + 1 := by simpa [diffCounts_length] using hk
by_cases hkn : k ≤ n
· have hklen : k ≤ (diffCounts x n).length := by
simpa [diffCounts_length] using hkn
rw [diffCounts, pref_append_singleton_le hklen]
exact ih (fun i hi => hnonneg i (by omega)) k
(by simpa [diffCounts_length] using hkn)
· have hkeq : k = n + 1 := by omega
subst k
rw [diffCounts, show n + 1 = (diffCounts x n).length + 1 by
rw [diffCounts_length]]
rw [pref_append_singleton_self, pref_length, diffCounts_length]
have hprev := ih (fun i hi => hnonneg i (by omega)) n
(by simp [diffCounts_length])
have hprefsum : pref (diffCounts x n) n = (diffCounts x n).sum :=
pref_eq_sum_of_length_le (by rw [diffCounts_length])
have hprev' : x n - x 0 = ((diffCounts x n).sum : ℤ) := by
simpa only [Nat.zero_add, hprefsum] using hprev
have hd : ((x (n + 1) - x n).toNat : ℤ) = x (n + 1) - x n := by
rw [Int.toNat_of_nonneg (hnonneg n (by omega))]
have hmap : (List.map Nat.cast (diffCounts x n)).sum =
((diffCounts x n).sum : ℤ) :=
(map_list_sum Int.ofNatHom (diffCounts x n)).symm
push_cast
rw [hmap, hd]
simp only [Nat.zero_add]
linarith
/-- The cumulative assignment reconstructed from its differences agrees with
`countsToX`. -/
theorem eq_countsToX_of_prefixCum {x : ℕ → ℤ} {counts : List ℕ} {n topCount : ℕ}
(h0 : x 0 = 0) (hlen : counts.length = n)
(hpref : PrefixCum x 0 counts)
(htop : topCount = (x (n + 1) - x n).toNat)
(hnonneg : 0 ≤ x (n + 1) - x n) :
∀ i ≤ n + 1, x i = countsToX n counts topCount i := by
intro i hi
by_cases hin : i = n + 1
· subst i
simp only [countsToX]
have hsum : x n = (pref counts n : ℤ) := by
have := hpref n (by omega)
simpa [h0] using this
have hsum' : x n = (pref counts counts.length : ℤ) := by
simpa [← hlen] using hsum
have hsumsum : (counts.sum : ℤ) = x n := by
rw [pref_length] at hsum'
exact hsum'.symm
have hd : ((x (n + 1) - x n).toNat : ℤ) = x (n + 1) - x n :=
Int.toNat_of_nonneg hnonneg
have hmap : (List.map Nat.cast counts).sum = (counts.sum : ℤ) :=
(map_list_sum Int.ofNatHom counts).symm
rw [htop]
push_cast
rw [hmap, hsumsum, hd]
ring
· have hi' : i ≤ n := by omega
have hne : i ≠ n + 1 := hin
simp only [countsToX, ite_eq_right hne]
have := hpref i (by omega)
simpa [h0] using this
/-- The branch equality edges say exactly that the toggle indicator is the chosen
branch value. -/
theorem branchEqEdges_holds_iff {bounds : List Key} {counts : List ℕ}
{topCount : ℕ} {k : Key} {stored : Bool} {x : ℕ → ℤ}
(hx : ∀ e : WithTop Key, EndpointCovered e bounds → x (endpointIndex bounds e) =
evalCount bounds counts topCount e)
(hk : k = ([] : Key) ∨ k ∈ bounds)
(hka : keyAfter k ∈ bounds) :
HoldsAll x (branchEqEdges bounds k stored) ↔
evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = (if stored then 1 else 0) := by
have hcovK : EndpointCovered (k : WithTop Key) bounds := by
rcases hk with rfl | hk
· exact Or.inl rfl
· exact Or.inr (Or.inr ⟨k, hk, rfl⟩)
have hcovKa : EndpointCovered ((keyAfter k : Key) : WithTop Key) bounds :=
Or.inr (Or.inr ⟨keyAfter k, hka, rfl⟩)
have hxi : x (endpointIndex bounds (k : WithTop Key)) =
evalCount bounds counts topCount (k : WithTop Key) := hx _ hcovK
have hxj : x (endpointIndex bounds ((keyAfter k : Key) : WithTop Key)) =
evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) := hx _ hcovKa
unfold branchEqEdges
cases stored
· change HoldsAll x
[⟨endpointIndex bounds (k : WithTop Key),
endpointIndex bounds ((keyAfter k : Key) : WithTop Key), 0⟩,
⟨endpointIndex bounds ((keyAfter k : Key) : WithTop Key),
endpointIndex bounds (k : WithTop Key), 0⟩] ↔
evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = 0
constructor
· intro h
have h1 := h ⟨endpointIndex bounds (k : WithTop Key),
endpointIndex bounds ((keyAfter k : Key) : WithTop Key), 0⟩ (by simp)
have h2 := h ⟨endpointIndex bounds ((keyAfter k : Key) : WithTop Key),
endpointIndex bounds (k : WithTop Key), 0⟩ (by simp)
simp only [DEdge.Holds] at h1 h2
rw [hxi, hxj] at h1 h2
linarith
· intro h e he
simp only [List.mem_cons, List.not_mem_nil, or_false] at he
rcases he with rfl | rfl
· simp only [DEdge.Holds]
rw [hxi, hxj]
linarith
· simp only [DEdge.Holds]
rw [hxi, hxj]
linarith
· change HoldsAll x
[⟨endpointIndex bounds (k : WithTop Key),
endpointIndex bounds ((keyAfter k : Key) : WithTop Key), 1⟩,
⟨endpointIndex bounds ((keyAfter k : Key) : WithTop Key),
endpointIndex bounds (k : WithTop Key), -1⟩] ↔
evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = 1
constructor
· intro h
have h1 := h ⟨endpointIndex bounds (k : WithTop Key),
endpointIndex bounds ((keyAfter k : Key) : WithTop Key), 1⟩ (by simp)
have h2 := h ⟨endpointIndex bounds ((keyAfter k : Key) : WithTop Key),
endpointIndex bounds (k : WithTop Key), -1⟩ (by simp)
simp only [DEdge.Holds] at h1 h2
rw [hxi, hxj] at h1 h2
linarith
· intro h e he
simp only [List.mem_cons, List.not_mem_nil, or_false] at he
rcases he with rfl | rfl
· simp only [DEdge.Holds]
rw [hxi, hxj]
linarith
· simp only [DEdge.Holds]
rw [hxi, hxj]
linarith
/-- Every nonnegativity edge of the capacity system is present. -/
theorem nonnegEdge_mem_capEdgesAux (start : Key) (bounds : List Key) (i j : ℕ)
(hj : j < bounds.length) :
(⟨i + j + 1, i + j, 0⟩ : DEdge) ∈ capEdgesAux start bounds i := by
induction bounds generalizing start i j with
| nil => simp at hj
| cons b bs ih =>
cases j with
| zero =>
simp [capEdgesAux]
| succ j' =>
have hj' : j' < bs.length := by simpa using hj
have hmem := ih b (i + 1) j' hj'
simp only [capEdgesAux, List.mem_append]
right
have h1 : i + (j' + 1) = i + 1 + j' := by omega
have h2 : i + (j' + 1) + 1 = i + 1 + j' + 1 := by omega
simpa [h1, h2] using hmem
/-- One branch of the finite count relaxation is feasible exactly when its
difference system is. -/
theorem countFeasibleBranch_iff_diffFeasible
(bounds : List Key) (k : Key) (stored : Bool)
(S : ConstraintSystem) (bad : List Constraint)
(hnoBot : ([] : Key) ∉ bounds) (hle : BoundsLe ([] : Key) bounds)
(hcoverS : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hcoverBad : ∀ c ∈ bad, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hk : k = ([] : Key) ∨ k ∈ bounds) (hka : keyAfter k ∈ bounds) :
CountFeasibleBranch bounds k stored S bad ↔
DiffFeasible [] (countDiffEdges bounds k stored S bad) := by
classical
constructor
· rintro ⟨counts, topCount, hfit, hS, hxd, hbad⟩
have hlen : counts.length = bounds.length := length_eq_of_countsFit hfit
let x : ℕ → ℤ := countsToX bounds.length counts topCount
have hxEval : ∀ e : WithTop Key, EndpointCovered e bounds →
x (endpointIndex bounds e) = evalCount bounds counts topCount e := by
intro e he
exact (evalCount_eq_countsToX hlen hnoBot he).symm
have hpref : PrefixCum x 0 counts :=
prefixCum_countsToX bounds.length counts topCount hlen
have hcapAux : HoldsAll x (capEdgesAux ([] : Key) bounds 0) :=
capEdgesAux_holds_of_countsFit hfit hlen hpref
have htopEdge : HoldsAll x [⟨bounds.length + 1, bounds.length, 0⟩] := by
intro e he
simp only [List.mem_singleton] at he
rw [he]
simp only [DEdge.Holds]
have hxn : x bounds.length = (counts.sum : ℤ) := by
dsimp [x]
rw [countsToX, ite_eq_right (by omega)]
rw [pref_eq_sum_of_length_le (l := counts) (n := bounds.length) (by omega)]
have hxt : x (bounds.length + 1) = ((counts.sum + topCount : ℕ) : ℤ) := by
dsimp [x]
rw [countsToX, ite_eq_left rfl]
push_cast
ring
rw [hxn, hxt]
push_cast
omega
have hcap : HoldsAll x (capEdges bounds) := by
intro e he
rw [capEdges, List.mem_append] at he
rcases he with he | he
· exact hcapAux e he
· exact htopEdge e he
have hcon : HoldsAll x (constraintEdges bounds S) :=
(constraintEdges_holds_iff hlen hxEval hcoverS).mpr hS
have hbadH : HoldsAll x (badEdges bounds k stored bad) :=
(badEdges_holds_iff hxd hxEval hcoverBad).mpr hbad
have hbr : HoldsAll x (branchEqEdges bounds k stored) :=
(branchEqEdges_holds_iff hxEval hk hka).mpr hxd
refine ⟨x, by simp [HoldsConsts], ?_⟩
intro e he
simp only [countDiffEdges, List.mem_append] at he
rcases he with ((he | he) | he) | he
· exact hcap e he
· exact hcon e he
· exact hbadH e he
· exact hbr e he
· rintro ⟨x, -, hx⟩
let y : ℕ → ℤ := fun i => x i - x 0
have hy : HoldsAll y (countDiffEdges bounds k stored S bad) := by
intro e he
have hx' := hx e he
simp only [DEdge.Holds] at hx' ⊢
dsimp [y]
linarith
have hcap : HoldsAll y (capEdges bounds) := by
intro e he
apply hy e
simp only [countDiffEdges, List.mem_append]
exact Or.inl (Or.inl (Or.inl he))
have hcon : HoldsAll y (constraintEdges bounds S) := by
intro e he
apply hy e
simp only [countDiffEdges, List.mem_append]
exact Or.inl (Or.inl (Or.inr he))
have hbadH : HoldsAll y (badEdges bounds k stored bad) := by
intro e he
apply hy e
simp only [countDiffEdges, List.mem_append]
exact Or.inl (Or.inr he)
have hbr : HoldsAll y (branchEqEdges bounds k stored) := by
intro e he
apply hy e
simp only [countDiffEdges, List.mem_append]
exact Or.inr he
have hcapAux : HoldsAll y (capEdgesAux ([] : Key) bounds 0) := by
intro e he
exact hcap e (List.mem_append.mpr (Or.inl he))
have hnonneg : ∀ i < bounds.length, 0 ≤ y (i + 1) - y i := by
intro i hi
have hmem := nonnegEdge_mem_capEdgesAux ([] : Key) bounds 0 i hi
have hmem' : (⟨i + 1, i, 0⟩ : DEdge) ∈ capEdges bounds :=
List.mem_append.mpr (Or.inl (by simpa using hmem))
have := hcap _ hmem'
simpa [DEdge.Holds] using this
have htopNonneg : 0 ≤ y (bounds.length + 1) - y bounds.length := by
have hmem : (⟨bounds.length + 1, bounds.length, 0⟩ : DEdge) ∈ capEdges bounds := by
simp [capEdges]
have := hcap _ hmem
simpa [DEdge.Holds] using this
let counts : List ℕ := diffCounts y bounds.length
let topCount : ℕ := (y (bounds.length + 1) - y bounds.length).toNat
have hlen : counts.length = bounds.length := diffCounts_length y bounds.length
have h0 : y 0 = 0 := by simp [y]
have hpref : PrefixCum y 0 counts :=
prefixCum_diffCounts h0 bounds.length hnonneg
have hfit : CountsFit ([] : Key) bounds counts :=
countsFit_of_capEdgesAux hle hlen hpref hcapAux
have htopEq : topCount = (y (bounds.length + 1) - y bounds.length).toNat := rfl
have hyAgree : ∀ i ≤ bounds.length + 1,
y i = countsToX bounds.length counts topCount i :=
eq_countsToX_of_prefixCum h0 hlen hpref htopEq htopNonneg
have hxEval : ∀ e : WithTop Key, EndpointCovered e bounds →
y (endpointIndex bounds e) = evalCount bounds counts topCount e := by
intro e he
have hidx : endpointIndex bounds e ≤ bounds.length + 1 := by
rcases he with rfl | rfl | ⟨a, ha, rfl⟩
· simp [endpointIndex]
· simp [endpointIndex]
· have ha' : a ≠ ([] : Key) := by
intro hbot
exact hnoBot (hbot ▸ ha)
have hlt : bounds.idxOf a < bounds.length := List.idxOf_lt_length_iff.mpr ha
simp only [endpointIndex, ha', ite_false]
omega
rw [hyAgree _ hidx]
exact (evalCount_eq_countsToX hlen hnoBot he).symm
have hS : SystemHoldsWithCounts S bounds counts topCount :=
(constraintEdges_holds_iff hlen hxEval hcoverS).mp hcon
have hxd : evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) -
evalCount bounds counts topCount (k : WithTop Key) = (if stored then 1 else 0) :=
(branchEqEdges_holds_iff hxEval hk hka).mp hbr
have hbad : ∀ c ∈ bad, c.bound <
evalCountToggled bounds counts topCount k c.hi -
evalCountToggled bounds counts topCount k c.lo :=
(badEdges_holds_iff hxd hxEval hcoverBad).mp hbadH
exact ⟨counts, topCount, hfit, hS, hxd, hbad⟩
/-- The unbranched finite-count feasibility predicate appearing in
`flipWitness_iff_exists_counts_canonical`. -/
def CountFeasible (bounds : List Key) (k : Key)
(S : ConstraintSystem) (bad : List Constraint) : Prop :=
∃ counts : List ℕ, ∃ topCount : ℕ,
CountsFit ([] : Key) bounds counts ∧
SystemHoldsWithCounts S bounds counts topCount ∧
∀ c ∈ bad, c.bound <
evalCountToggled bounds counts topCount k c.hi -
evalCountToggled bounds counts topCount k c.lo
/-- The unbranched count predicate is the disjunction of the two toggle-indicator
branches. -/
theorem countFeasible_iff_branch_or
(bounds : List Key) (k : Key) (S : ConstraintSystem) (bad : List Constraint)
(hnoBot : ([] : Key) ∉ bounds)
(_hcoverS : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(_hcoverBad : ∀ c ∈ bad, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hk : k = ([] : Key) ∨ k ∈ bounds) (hka : keyAfter k ∈ bounds) :
CountFeasible bounds k S bad ↔
CountFeasibleBranch bounds k true S bad ∨
CountFeasibleBranch bounds k false S bad := by
constructor
· rintro ⟨counts, topCount, hfit, hS, hbad⟩
obtain ⟨db, hcountsAt, htop⟩ := exists_db_realizing_counts bounds counts topCount hfit
have hcovK : EndpointCovered (k : WithTop Key) bounds := by
rcases hk with rfl | hk
· exact Or.inl rfl
· exact Or.inr (Or.inr ⟨k, hk, rfl⟩)
have hcovKa : EndpointCovered ((keyAfter k : Key) : WithTop Key) bounds :=
Or.inr (Or.inr ⟨keyAfter k, hka, rfl⟩)
have hkEval : evalCount bounds counts topCount (k : WithTop Key) = cnt db (k : WithTop Key) :=
evalCount_eq_cnt_of_covered hcountsAt htop hnoBot hcovK
have hkaEval : evalCount bounds counts topCount ((keyAfter k : Key) : WithTop Key) =
cnt db ((keyAfter k : Key) : WithTop Key) :=
evalCount_eq_cnt_of_covered hcountsAt htop hnoBot hcovKa
by_cases hmem : k ∈ db.keys
· refine Or.inl ⟨counts, topCount, hfit, hS, ?_, hbad⟩
rw [hkEval, hkaEval]
simpa [hmem] using cnt_keyAfter_sub_cnt db k
· refine Or.inr ⟨counts, topCount, hfit, hS, ?_, hbad⟩
rw [hkEval, hkaEval]
simpa [hmem] using cnt_keyAfter_sub_cnt db k
· rintro (⟨counts, topCount, hfit, hS, -, hbad⟩ |
⟨counts, topCount, hfit, hS, -, hbad⟩)
· exact ⟨counts, topCount, hfit, hS, hbad⟩
· exact ⟨counts, topCount, hfit, hS, hbad⟩
/-- Computable decision of the unbranched finite-count feasibility. -/
def countFeasibleBool (bounds : List Key) (k : Key)
(S : ConstraintSystem) (bad : List Constraint) : Bool :=
diffFeasibleBoolAuto (countDiffEdges bounds k false S bad) ||
diffFeasibleBoolAuto (countDiffEdges bounds k true S bad)
theorem countFeasibleBool_spec (bounds : List Key) (k : Key)
(S : ConstraintSystem) (bad : List Constraint)
(hnoBot : ([] : Key) ∉ bounds) (hle : BoundsLe ([] : Key) bounds)
(hcoverS : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hcoverBad : ∀ c ∈ bad, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hk : k = ([] : Key) ∨ k ∈ bounds) (hka : keyAfter k ∈ bounds) :
countFeasibleBool bounds k S bad = true ↔ CountFeasible bounds k S bad := by
have hfalse := countFeasibleBranch_iff_diffFeasible bounds k false S bad
hnoBot hle hcoverS hcoverBad hk hka
have htrue := countFeasibleBranch_iff_diffFeasible bounds k true S bad
hnoBot hle hcoverS hcoverBad hk hka
rw [countFeasibleBool, Bool.or_eq_true, diffFeasibleBoolAuto_spec,
diffFeasibleBoolAuto_spec, ← hfalse, ← htrue]
rw [countFeasible_iff_branch_or bounds k S bad hnoBot hcoverS hcoverBad hk hka]
tauto
/-- All finite choices of one constraint from each alternative of a DNF. -/
def choices : ConstraintDNF → List (List Constraint)
| [] => [[]]
| S :: Ss => S.flatMap fun c => (choices Ss).map fun bs => c :: bs
theorem mem_choices {D : ConstraintDNF} {bad : List Constraint} :
bad ∈ choices D ↔ ChoosesAll bad D := by
induction D generalizing bad with
| nil =>
cases bad <;> simp [choices, ChoosesAll]
| cons S Ss ih =>
cases bad with
| nil =>
simp [choices, ChoosesAll]
| cons c cs =>
simp only [choices, List.mem_flatMap, List.mem_map, ChoosesAll, ih]
constructor
· rintro ⟨a, ha, bs, hbs, heq⟩
cases heq
exact ⟨ha, hbs⟩
· rintro ⟨ha, hcs⟩
exact ⟨c, ha, cs, hcs, rfl⟩
/-- Computable version of `RangeRead.withinLimit`. -/
def withinLimitBool (r : RangeRead) (ks : List Key) : Bool :=
match r.limit with
| none => true
| some n => decide (ks.length ≤ (n : ℕ))
theorem withinLimitBool_eq (r : RangeRead) (ks : List Key) :
withinLimitBool r ks = true ↔ RangeRead.withinLimit r ks := by
cases h : r.limit with
| none => simp [withinLimitBool, RangeRead.withinLimit, h]
| some n => simp [withinLimitBool, RangeRead.withinLimit, h]
/-- The computable activity oracle. It enumerates the DNF alternatives and the
finite choices of one violated constraint per alternative, then invokes the
difference-constraint decider for the canonical endpoint list `activeBounds`. -/
def activeComputable (r : RangeRead) (res : Result) (k : Key) : Bool :=
let D := characterizingDNF r res
let bounds := activeBounds D k
withinLimitBool r res.keys &&
D.any fun S => (choices D).any fun bad => countFeasibleBool bounds k S bad
/-- The computable activity oracle is exact: it returns `true` exactly for the
one-key flip witnesses. This closes the algorithmic interface left open in
`General.lean`. -/
theorem activeComputable_spec {r : RangeRead} {res : Result}
(hread : Readable r res) :
ActiveDecider r res (activeComputable r res) := by
intro k
let D := characterizingDNF r res
let bounds := activeBounds D k
have hnoBot : ([] : Key) ∉ bounds := not_mem_activeBounds_bot D k
have hle : BoundsLe ([] : Key) bounds := activeBounds_boundsLe D k
have hcoverD : ∀ S ∈ D, ∀ c ∈ S,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro S hS c hc
exact dnfEndpointCovered_activeBounds hS hc
have hk : k = ([] : Key) ∨ k ∈ bounds := by
by_cases hkbot : k = ([] : Key)
· exact Or.inl hkbot
· exact Or.inr (by
rw [mem_activeBounds]
exact Or.inr (Or.inr ⟨hkbot, rfl⟩))
have hka : keyAfter k ∈ bounds := by
rw [mem_activeBounds]
exact Or.inl rfl
rw [activeComputable]
rw [Bool.and_eq_true, withinLimitBool_eq, List.any_eq_true]
constructor
· rintro ⟨hw, S, hS, hchoiceTrue⟩
rw [List.any_eq_true] at hchoiceTrue
obtain ⟨bad, hbadMem, hfeas⟩ := hchoiceTrue
have hchooses : ChoosesAll bad D := mem_choices.mp hbadMem
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem hchooses hc
exact hcoverD S' hS' c hcS'
have hcount : CountFeasible bounds k S bad :=
(countFeasibleBool_spec bounds k S bad hnoBot hle (hcoverD S hS) hcoverBad hk hka).mp
hfeas
exact (flipWitness_iff_exists_counts_canonical (D := D)
(characterizesDNF_characterizingDNF hread)).mpr
⟨hw, S, hS, bad, hchooses, hcount⟩
· intro hw
rcases (flipWitness_iff_exists_counts_canonical (D := D)
(characterizesDNF_characterizingDNF hread)).mp hw with
⟨hwithin, S, hS, bad, hchooses, hcount⟩
refine ⟨hwithin, ⟨S, hS, ?_⟩⟩
rw [List.any_eq_true]
refine ⟨bad, mem_choices.mpr hchooses, ?_⟩
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem hchooses hc
exact hcoverD S' hS' c hcS'
exact (countFeasibleBool_spec bounds k S bad hnoBot hle (hcoverD S hS) hcoverBad hk hka).mpr
hcount
/-- The cellwise algorithm with the computable oracle is minimal on every readable
pair. -/
theorem conflictRangeCellwise_minimal_computable {r : RangeRead} {res : Result}
(hread : Readable r res) :
Minimal r res (conflictRangeCellwise r res (activeComputable r res)) :=
conflictRangeCellwise_minimal (activeComputable_spec hread) hread
/-- The computable-oracle cellwise algorithm computes exactly the necessary set. -/
theorem conflictRangeCellwise_toSet_eq_necessarySet_computable
{r : RangeRead} {res : Result} (hread : Readable r res) :
(conflictRangeCellwise r res (activeComputable r res)).toSet = necessarySet r res :=
conflictRangeCellwise_toSet_eq_necessarySet (activeComputable_spec hread) hread
end FormalConflictRange