Structural additive gap for bin packing, part 8 of 10 (port of OpenAI's formalization)
DefinitionOAI_BinPackingGap_Part08Part 8 of 10 of a port of OpenAI's Lean formalization of the structural additive gap from the manuscript Additive hardness and unbounded configuration gaps in bin packing (OpenAI, September 24, 2026). For every , it constructs an instance with items of sizes in whose individual and type configuration LPs both equal , while the optimum exceeds . This part contains the modules Trees/InventoryFromTrees, Inventory/LocalCompletionCoverage, Inventory/PackingExclusions, Trees/InventoryRowGeometry, Machines/PackingJobCoverage, Configurations/CoverageSoundness, Trees/TreeAvoidance, Packing/PhaseIteration, Trees/CompetingTrees, Packing/ExtractedCover.
Attribution. The code is adapted from the OpenAI "math" repository, commit adc7f1241b42e322a6451854ab7e4b4c146bf78a, directory lean/OAI/Computability/BinPacking. It is © OpenAI and licensed under the Apache License 2.0; the adapted code is redistributed under the same license.
Modifications. Modules are concatenated in dependency order, with their imports replaced by the previous part. The model definitions come from the platform definition BinPackingGap, which matches upstream Model.lean up to two private lemmas and a section wrapper. This part sets maxHeartbeats to 1000000, because the platform compiler exceeded the default heartbeat limit on a simp call that stays far below it locally.
The development is split into 10 parts only so that each compiles within the platform's time limit. The final part proves OAI.BinPackingGap.structural_additive_gap, the first clause of OAI.BinPackingGap.main_results.
/-
Structural additive gap for bin packing (port of OpenAI's formalization), part 8 of 10.
Adapted from the OpenAI "math" repository (https://github.com/openai/math, commit
adc7f1241b42e322a6451854ab7e4b4c146bf78a), lean/OAI/Computability/BinPacking/: Trees/InventoryFromTrees.lean, Inventory/LocalCompletionCoverage.lean, Inventory/PackingExclusions.lean, Trees/InventoryRowGeometry.lean, Machines/PackingJobCoverage.lean, Configurations/CoverageSoundness.lean, Trees/TreeAvoidance.lean, Packing/PhaseIteration.lean, Trees/CompetingTrees.lean, Packing/ExtractedCover.lean
These files formalize part of the manuscript "Additive hardness and unbounded configuration gaps in
bin packing" (OpenAI, September 24, 2026). Copyright OpenAI. Licensed under the Apache License,
Version 2.0 (http://www.apache.org/licenses/LICENSE-2.0); the adapted code is distributed under the same
license, on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND.
Modifications: modules concatenated in dependency order with their import lines removed; the model
definitions (Model.lean) come from the platform definition `BinPackingGap`, to which upstream Model.lean
is identical up to two private lemmas and a section wrapper; `set_option maxHeartbeats 1000000` is set for this part (the platform compiler exceeded the default heartbeat limit on a `simp` call that stays far below it locally).
-/
import Mathlib
import Definitions.Def_OAI_BinPackingGap_Part07
set_option autoImplicit false
set_option maxHeartbeats 1000000
-- ===== Adapted from lean/OAI/Computability/BinPacking/Trees/InventoryFromTrees.lean =====
namespace OAI
namespace BinPackingGap.InventoryData
def ofCompetingTrees (G : GraphInput) {d : ℕ} (T : CompetingTrees d) (R k : ℕ) :
InventoryData where
graph := G
plus := T.plus
minus := T.minus
d := d
R := R
L := T.height
quota := T.quota
k := k
@[simp] theorem ofCompetingTrees_P (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) :
(ofCompetingTrees G T R k).P = T.quotaTotal := rfl
theorem ofCompetingTrees_plus_height (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) :
(ofCompetingTrees G T R k).plus.height = (ofCompetingTrees G T R k).L :=
T.plus_height
theorem ofCompetingTrees_minus_height (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) :
(ofCompetingTrees G T R k).minus.height = (ofCompetingTrees G T R k).L :=
T.minus_height
theorem ofCompetingTrees_height_pos (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) : 0 < (ofCompetingTrees G T R k).L :=
T.height_pos
end BinPackingGap.InventoryData
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Inventory/LocalCompletionCoverage.lean =====
namespace OAI
noncomputable section
namespace BinPackingGap.PartialAllocation
theorem exists_equiv_extending_embeddings
{I J S : Type*} [Fintype I] [Fintype J]
(f : S ↪ I) (g : S ↪ J)
(hcard : Fintype.card I = Fintype.card J) :
∃ e : I ≃ J, ∀ s, e (f s) = g s := by
classical
let assigned : Set.range f ≃ Set.range g :=
(Equiv.ofInjective f f.injective).symm.trans (Equiv.ofInjective g g.injective)
have hremaining : Fintype.card ↥((Set.range f)ᶜ) =
Fintype.card ↥((Set.range g)ᶜ) := by
rw [Fintype.card_compl_set, Fintype.card_compl_set, hcard,
Fintype.card_congr assigned]
let remaining : ↥((Set.range f)ᶜ) ≃ ↥((Set.range g)ᶜ) :=
Fintype.equivOfCardEq hremaining
let e : I ≃ J := (Equiv.Set.sumCompl (Set.range f)).symm.trans
((Equiv.sumCongr assigned remaining).trans (Equiv.Set.sumCompl (Set.range g)))
refine ⟨e, ?_⟩
intro s
have hfs : f s ∈ Set.range f := ⟨s, rfl⟩
change ((Equiv.Set.sumCompl (Set.range g))
((Equiv.sumCongr assigned remaining)
((Equiv.Set.sumCompl (Set.range f)).symm (f s)))) = g s
rw [Equiv.Set.sumCompl_symm_apply_of_mem hfs]
simp only [Equiv.sumCongr_apply, Sum.map_inl, Equiv.Set.sumCompl_apply_inl]
change ((Equiv.ofInjective g g.injective)
((Equiv.ofInjective f f.injective).symm ⟨f s, hfs⟩)).val = g s
rw [Equiv.ofInjective_symm_apply]
rfl
theorem exists_equiv_extending_injections
{I J S : Type*} [Fintype I] [Fintype J]
(f : S → I) (g : S → J) (hf : Function.Injective f) (hg : Function.Injective g)
(hcard : Fintype.card I = Fintype.card J) :
∃ e : I ≃ J, ∀ s, e (f s) = g s :=
exists_equiv_extending_embeddings ⟨f, hf⟩ ⟨g, hg⟩ hcard
end BinPackingGap.PartialAllocation
namespace BinPackingGap.InventoryData
open IntervalCoverage
variable (D : InventoryData)
theorem designated_injective (v : D.Vertex) :
Function.Injective (D.designated (v := v)) := by
rintro ⟨(p | p | j), a⟩ ⟨(q | q | k), b⟩ h <;>
simp_all [designated, Subtype.val_inj]
theorem deadline_undesignated {v : D.Vertex} (i : D.MBase v)
(hi : ∀ q : D.TestAt v × Fin D.d, D.designated q ≠ i) :
D.deadline i = D.mainBaseline i := by
rcases i with (⟨node, j⟩ | ⟨node, j⟩ | padding) | job
· have hn : node.val ∉ D.plus.leaves := by
intro hn
exact hi (.inl ⟨node, hn⟩, j) rfl
simp only [deadline, treeDeadline, hn, ite_false, mainBaseline, treeBaseline]
· have hn : node.val ∉ D.minus.leaves := by
intro hn
exact hi (.inr (.inl ⟨node, hn⟩), j) rfl
simp only [deadline, treeDeadline, hn, ite_false, mainBaseline, treeBaseline]
· rfl
· exact False.elim (hi (.inr (.inr job.1), job.2) rfl)
def deadlineShiftData (v : D.Vertex) :
ShiftData (D.MBase v) (D.TestAt v) D.d ℚ where
baseline := D.mainBaseline
left := D.testLeft
right := D.testRight
designated := ⟨D.designated, D.designated_injective v⟩
baseline_designated := D.mainBaseline_designated
left_le_right := fun t => (D.testLeft_lt_testRight t).le
private theorem deadline_prefix_active (v : D.Vertex) (a : ℚ) :
prefixCount (D.deadline (v := v)) a =
prefixCount (D.mainBaseline (v := v)) a +
D.d * ((D.deadlineShiftData v).activeTests a).card := by
exact (D.deadlineShiftData v).deadline_prefix_of_agrees
(D.deadline (v := v)) D.deadline_designated D.deadline_undesignated a
private theorem deadline_active_card (hplusheight : D.plus.height = D.L)
(hminusheight : D.minus.height = D.L) (hL : 1 ≤ D.L)
(v : D.Vertex) (a : ℚ) :
((D.deadlineShiftData v).activeTests a).card =
@ite ℕ (∃ t : D.TestAt v, a ∈ D.testInterval t)
(Classical.propDecidable _) 1 0 := by
classical
have hdisjoint : ∀ s t : D.TestAt v, s ≠ t →
Disjoint (Set.Ico ((D.deadlineShiftData v).left s)
((D.deadlineShiftData v).right s))
(Set.Ico ((D.deadlineShiftData v).left t)
((D.deadlineShiftData v).right t)) := by
intro s t hst
exact D.testInterval_disjoint hplusheight hminusheight hL hst
have hc := (D.deadlineShiftData v).activeTests_card hdisjoint a
by_cases ht : ∃ t : D.TestAt v, a ∈ D.testInterval t
· rw [ite_eq_left ht]
have ht' : ∃ t : D.TestAt v,
(D.deadlineShiftData v).left t ≤ a ∧
a < (D.deadlineShiftData v).right t := ht
rw [ite_eq_left ht'] at hc
exact hc
· rw [ite_eq_right ht]
have ht' : ¬ ∃ t : D.TestAt v,
(D.deadlineShiftData v).left t ≤ a ∧
a < (D.deadlineShiftData v).right t := ht
rw [ite_eq_right ht'] at hc
exact hc
theorem deadline_prefix (hplusheight : D.plus.height = D.L)
(hminusheight : D.minus.height = D.L) (hL : 1 ≤ D.L)
(v : D.Vertex) (a : ℚ) :
prefixCount (D.deadline (v := v)) a =
prefixCount (D.mainBaseline (v := v)) a +
D.d * (@ite ℕ (∃ t : D.TestAt v, a ∈ D.testInterval t)
(Classical.propDecidable _) 1 0) := by
rw [D.deadline_prefix_active, D.deadline_active_card hplusheight hminusheight hL]
theorem deadline_prefix_at_test (hplusheight : D.plus.height = D.L)
(hminusheight : D.minus.height = D.L) (hL : 1 ≤ D.L)
(v : D.Vertex) (t : D.TestAt v) (a : ℚ) (ha : a ∈ D.testInterval t) :
((Finset.univ : Finset (D.MBase v)).filter (fun z => D.deadline z ≤ a)).card =
((Finset.univ : Finset (D.MBase v)).filter
(fun z => D.mainBaseline z ≤ a)).card + D.d := by
classical
have hex : ∃ t : D.TestAt v, a ∈ D.testInterval t := ⟨t, ha⟩
simpa only [prefixCount, prefixSet, ite_eq_left hex, Nat.mul_one] using
D.deadline_prefix hplusheight hminusheight hL v a
theorem exists_deadline_matching (hplusheight : D.plus.height = D.L)
(hminusheight : D.minus.height = D.L) (hL : 1 ≤ D.L)
(v : D.Vertex) (h : D.MBase v → ℚ)
(hle : ∀ b, h b ≤ D.mainBaseline b)
(hcover : ∀ (t : D.TestAt v) (a : ℚ), a ∈ D.testInterval t →
D.d ≤ coverageCount h D.mainBaseline a) :
∃ e : D.MBase v ≃ D.MBase v, ∀ b, h b ≤ D.deadline (e b) := by
classical
apply exists_equiv_of_prefix_dominance h D.deadline rfl
intro a
rw [D.deadline_prefix hplusheight hminusheight hL,
completion_prefix_identity h D.mainBaseline hle]
by_cases ht : ∃ t : D.TestAt v, a ∈ D.testInterval t
· rw [ite_eq_left ht, Nat.mul_one]
obtain ⟨t, ht⟩ := ht
exact Nat.add_le_add_left (hcover t a ht) _
· rw [ite_eq_right ht, Nat.mul_zero, Nat.add_zero]
exact Nat.le_add_right _ _
end BinPackingGap.InventoryData
namespace BinPackingGap.LocalResourceAllocation
open UniformTree
def oppositeTree {d : ℕ} (T : CompetingTrees d) : Bool → UniformTree
| false => T.plus
| true => T.minus
def oppositeMarking {d : ℕ} (T : CompetingTrees d) :
(selected : Bool) → Finset (oppositeTree T selected).Node
| false => T.markingPlus
| true => T.markingMinus
abbrev OppositeMarked {d : ℕ} (T : CompetingTrees d) (selected : Bool) :=
↥(oppositeMarking T selected)
theorem opposite_height {d : ℕ} (T : CompetingTrees d) (selected : Bool) :
(oppositeTree T selected).height = T.height := by
cases selected
· exact T.plus_height
· exact T.minus_height
theorem opposite_depth_pos {d : ℕ} (T : CompetingTrees d) (selected : Bool)
(a : OppositeMarked T selected) : 0 < depth a.val := by
cases selected
· exact T.markingPlus_depth_pos a.val a.property
· exact T.markingMinus_depth_pos a.val a.property
theorem opposite_quota {d : ℕ} (T : CompetingTrees d) (selected : Bool)
(ell : ℕ) (hlo : 1 ≤ ell) (hhi : ell ≤ T.height) :
((oppositeMarking T selected).filter (fun node => depth node = ell)).card ≤
T.quota ell := by
cases selected
· exact T.plus_quota ell hlo hhi
· exact T.minus_quota ell hlo hhi
variable (G : GraphInput) {d : ℕ} (T : CompetingTrees d) (hd : 0 < d) (R k : ℕ)
local notation "D" => InventoryData.ofCompetingTrees G T R k
def markedDepth (selected : Bool) (a : OppositeMarked T selected) : (D).Depth :=
⟨depth a.val, Finset.mem_Icc.mpr
⟨opposite_depth_pos T selected a,
(depth_le_height a.val).trans_eq (opposite_height T selected)⟩⟩
def markedByDepth (selected : Bool) : OppositeMarked T selected ↪
Σ ell : (D).Depth,
↥((oppositeMarking T selected).filter (fun node => depth node = ell.val)) := by
classical
refine ⟨fun a => ⟨markedDepth G T R k selected a,
⟨a.val, Finset.mem_filter.mpr ⟨a.property, rfl⟩⟩⟩, ?_⟩
intro a b hab
apply Subtype.ext
exact congrArg (fun z => z.2.val) hab
def markedResource (selected : Bool) : OppositeMarked T selected ↪ (D).PositiveLocal := by
classical
exact (markedByDepth G T R k selected).trans
(Function.Embedding.sigmaMap (Function.Embedding.refl (D).Depth) (fun ell =>
(Finset.equivFin
((oppositeMarking T selected).filter (fun node => depth node = ell.val))).toEmbedding.trans
(Fin.castLEEmb (opposite_quota T selected ell.val
(Finset.mem_Icc.mp ell.property).1 (Finset.mem_Icc.mp ell.property).2))))
@[simp] theorem markedResource_depth (selected : Bool) (a : OppositeMarked T selected) :
(markedResource G T R k selected a).1.val = depth a.val := rfl
def markedRow (v : G.Vertex) :
(selected : Bool) → OppositeMarked T selected → (D).MBase v
| false, a => .inl (.inl (a.val, ⟨0, hd⟩))
| true, a => .inl (.inr (.inl (a.val, ⟨0, hd⟩)))
theorem markedRow_injective (v : G.Vertex) (selected : Bool) :
Function.Injective (markedRow G T hd R k v selected) := by
cases selected
· intro a b hab
apply Subtype.ext
exact congrArg Prod.fst (Sum.inl.inj (Sum.inl.inj hab))
· intro a b hab
apply Subtype.ext
exact congrArg Prod.fst (Sum.inl.inj (Sum.inr.inj (Sum.inl.inj hab)))
theorem fundedRoot_ne_markedRow (v : G.Vertex) (selected : Bool) (j : Fin d)
(a : OppositeMarked T selected) :
(D).fundedRoot selected j ≠ markedRow G T hd R k v selected a := by
cases selected <;> intro h <;> cases Sum.inl.inj h
def zeroResource (v : G.Vertex) : Fin d ↪ (D).DMAt v := by
clear hd
have hstock : d ≤ (D).t - (D).P := by
have h := (D).two_mul_d_le_t_sub_P
change 2 * d ≤ (D).t - (D).P at h
omega
refine ⟨fun j => .inr (.inl (Fin.castLE hstock j)), ?_⟩
intro a b hab
exact Fin.castLE_injective hstock (Sum.inl.inj (Sum.inr.inj hab))
@[simp] theorem zeroResource_local_length (v : G.Vertex) (j : Fin d) :
(D).localLength (.inl (zeroResource G T R k v j)) = 0 := rfl
def seedRows (v : G.Vertex) (selected : Bool) :
(Fin d ⊕ OppositeMarked T selected) ↪ (D).MBase v := by
refine ⟨Sum.elim ((D).fundedRoot selected) (markedRow G T hd R k v selected), ?_⟩
intro a b hab
rcases a with a | a <;> rcases b with b | b
· exact congrArg Sum.inl ((D).fundedRoot_injective v selected hab)
· exact False.elim (fundedRoot_ne_markedRow G T hd R k v selected a b hab)
· exact False.elim (fundedRoot_ne_markedRow G T hd R k v selected b a hab.symm)
· exact congrArg Sum.inr (markedRow_injective G T hd R k v selected hab)
def seedResources (v : G.Vertex) (selected : Bool) :
(Fin d ⊕ OppositeMarked T selected) ↪ (D).DMAt v := by
refine ⟨Sum.elim (zeroResource G T R k v)
(fun a => .inl (markedResource G T R k selected a)), ?_⟩
intro a b hab
rcases a with a | a <;> rcases b with b | b
· exact congrArg Sum.inl ((zeroResource G T R k v).injective hab)
· have hbad : Sum.inr _ = Sum.inl _ := hab
cases hbad
· have hbad : Sum.inl _ = Sum.inr _ := hab
cases hbad
· exact congrArg Sum.inr ((markedResource G T R k selected).injective (Sum.inl.inj hab))
theorem exists_localEquiv (v : G.Vertex) (selected : Bool) :
∃ e : (D).MBase v ≃ (D).DMAt v,
∀ s : Fin d ⊕ OppositeMarked T selected,
e (seedRows G T hd R k v selected s) = seedResources G T R k v selected s := by
let : Fintype ((D).MBase v) := by
dsimp [InventoryData.MBase, InventoryData.TreeRow, InventoryData.JobCopy,
InventoryData.ofCompetingTrees]
infer_instance
let : Fintype ((D).DMAt v) := by
dsimp [InventoryData.DMAt, InventoryData.PositiveLocal, InventoryData.ZeroLocalAt,
InventoryData.Depth, InventoryData.JobCopy, InventoryData.ofCompetingTrees]
infer_instance
apply PartialAllocation.exists_equiv_extending_embeddings
(seedRows G T hd R k v selected) (seedResources G T R k v selected)
exact ((D).card_mBase v).trans ((D).card_dmAt v).symm
def localEquiv (v : G.Vertex) (selected : Bool) : (D).MBase v ≃ (D).DMAt v :=
Classical.choose (exists_localEquiv G T hd R k v selected)
theorem localEquiv_seed (v : G.Vertex) (selected : Bool)
(s : Fin d ⊕ OppositeMarked T selected) :
localEquiv G T hd R k v selected (seedRows G T hd R k v selected s) =
seedResources G T R k v selected s :=
Classical.choose_spec (exists_localEquiv G T hd R k v selected) s
theorem localEquiv_fundedRoot (v : G.Vertex) (selected : Bool) (j : Fin d) :
localEquiv G T hd R k v selected ((D).fundedRoot selected j) =
zeroResource G T R k v j :=
localEquiv_seed G T hd R k v selected (.inl j)
theorem localEquiv_markedRow (v : G.Vertex) (selected : Bool)
(a : OppositeMarked T selected) :
localEquiv G T hd R k v selected (markedRow G T hd R k v selected a) =
.inl (markedResource G T R k selected a) :=
localEquiv_seed G T hd R k v selected (.inr a)
theorem fundedRoot_local_zero (v : G.Vertex) (selected : Bool) (j : Fin d) :
(D).localLength (.inl (localEquiv G T hd R k v selected ((D).fundedRoot selected j))) =
0 := by
rw [localEquiv_fundedRoot, zeroResource_local_length]
theorem markedRow_local_length (v : G.Vertex) (selected : Bool)
(a : OppositeMarked T selected) :
(D).localLength (.inl (localEquiv G T hd R k v selected
(markedRow G T hd R k v selected a))) =
Geometry.lambda G.edges.length R (D).geometryBound (depth a.val) := by
rw [localEquiv_markedRow]
change Geometry.lambda G.edges.length R (D).geometryBound
(markedResource G T R k selected a).1.val = _
rw [markedResource_depth]
theorem plusMarked_local_length (v : G.Vertex) (node : T.plus.Node)
(hnode : node ∈ T.markingPlus) :
(D).localLength (.inl (localEquiv G T hd R k v false
(.inl (.inl (node, ⟨0, hd⟩))))) =
Geometry.lambda G.edges.length R (D).geometryBound (depth node) :=
markedRow_local_length G T hd R k v false ⟨node, hnode⟩
theorem minusMarked_local_length (v : G.Vertex) (node : T.minus.Node)
(hnode : node ∈ T.markingMinus) :
(D).localLength (.inl (localEquiv G T hd R k v true
(.inl (.inr (.inl (node, ⟨0, hd⟩)))))) =
Geometry.lambda G.edges.length R (D).geometryBound (depth node) :=
markedRow_local_length G T hd R k v true ⟨node, hnode⟩
end BinPackingGap.LocalResourceAllocation
namespace BinPackingGap.LocalCompletionCoverage
open InventoryData IntervalCoverage
private theorem card_le_coverage {ι κ : Type*} [Fintype ι]
(h baseline : ι → ℚ) (a : ℚ) (s : Finset κ) (f : κ → ι)
(hf : Function.Injective f)
(hc : ∀ x ∈ s, h (f x) ≤ a ∧ a < baseline (f x)) :
s.card ≤ coverageCount h baseline a := by
classical
exact Finset.card_le_card_of_injOn f
(fun x hx => (mem_coverageSet h baseline a (f x)).mpr (hc x hx))
(fun _ _ _ _ hxy => hf hxy)
private theorem nodeInterval_subset_root {U : UniformTree} (node : U.Node)
(m R B : ℕ) (side : TreeGeometry.Side) (hB : U.branchBound ≤ B)
{a : ℚ}
(ha : a ∈ Set.Ico (TreeGeometry.left m R B side node.val)
(TreeGeometry.right m R B side node.val)) :
a ∈ Set.Ico (TreeGeometry.rootOffset side) (TreeGeometry.rootOffset side + 1) := by
have he := TreeGeometry.prefix_endpoints m R B side
(u := []) (v := node.val) List.nil_prefix (TreeGeometry.boundedAddress_node node hB)
simp only [TreeGeometry.left_nil, TreeGeometry.right_nil] at he
exact ⟨he.1.trans ha.1, ha.2.trans_le he.2⟩
variable (G : GraphInput) {d : ℕ} (T : CompetingTrees d) (hd : 0 < d) (R k : ℕ)
local notation "D" => InventoryData.ofCompetingTrees G T R k
local instance mainFintype (v : G.Vertex) : Fintype ((D).MBase v) := by
dsimp [InventoryData.MBase, InventoryData.TreeRow, InventoryData.JobCopy,
InventoryData.ofCompetingTrees]
infer_instance
def localCompletion (v : G.Vertex) (selected : Bool) (b : (D).MBase v) : ℚ :=
(D).rowCoordinate ((D).stateMainRow v selected b) - (D).stateMainLength selected b -
(D).localLength (.inl (LocalResourceAllocation.localEquiv G T hd R k v selected b))
theorem localCompletion_le_baseline (v : G.Vertex) (selected : Bool) (b : (D).MBase v) :
localCompletion G T hd R k v selected b ≤ (D).mainBaseline b := by
have hg := (D).stateMainLength_nonneg selected b
have hl := (D).localLength_nonneg
(.inl (LocalResourceAllocation.localEquiv G T hd R k v selected b))
have hdelta := Geometry.delta_nonneg G.edges.length R (D).geometryBound (D).L
have hshort : (0 : ℚ) ≤
if (D).rowShort ((D).stateMainRow v selected b) then
Geometry.delta G.edges.length R (D).geometryBound (D).L else 0 := by
split_ifs
· exact hdelta
· exact le_rfl
have hbase := (D).stateMainRow_baseline v selected b
unfold localCompletion rowCoordinate
dsimp only [InventoryData.ofCompetingTrees] at *
rw [hbase]
linarith
private theorem fundedRoot_covers (v : G.Vertex) (selected : Bool) (j : Fin d)
{a : ℚ} (ha : a ∈ Set.Ico (if selected then 0 else 4) (if selected then 1 else 5)) :
localCompletion G T hd R k v selected ((D).fundedRoot selected j) ≤ a ∧
a < (D).mainBaseline ((D).fundedRoot (v := v) selected j) := by
have hzero := LocalResourceAllocation.fundedRoot_local_zero G T hd R k v selected j
have hglobal := (D).stateMainLength_fundedRoot (v := v) selected j
unfold localCompletion
rw [hzero, hglobal]
cases selected <;>
norm_num [fundedRoot, stateMainRow, stateRowEquiv, rowCoordinate, rowBaseline,
rowShort, mainBaseline, treeBaseline, UniformTree.root, TreeGeometry.right_nil,
TreeGeometry.rootOffset] at ha ⊢ <;> exact ha
private theorem fundedRoot_coverage (v : G.Vertex) (selected : Bool) {a : ℚ}
(ha : a ∈ Set.Ico (if selected then 0 else 4) (if selected then 1 else 5)) :
d ≤ coverageCount (localCompletion G T hd R k v selected) (D).mainBaseline a := by
classical
have hc := card_le_coverage (localCompletion G T hd R k v selected)
(D).mainBaseline a (Finset.univ : Finset (Fin d)) ((D).fundedRoot selected)
((D).fundedRoot_injective v selected)
(fun j _ => fundedRoot_covers G T hd R k v selected j ha)
simpa only [Finset.card_univ, Fintype.card_fin] using hc
private theorem plusMarked_completion_le (v : G.Vertex) (node : T.plus.Node)
(hnode : node ∈ T.markingPlus) :
localCompletion G T hd R k v false (.inl (.inl (node, ⟨0, hd⟩))) ≤
TreeGeometry.left G.edges.length R (D).geometryBound .plus node.val := by
have hlocal := LocalResourceAllocation.plusMarked_local_length G T hd R k v node hnode
have hglobal := (D).stateMainLength_nonneg false
(.inl (.inl (node, ⟨0, hd⟩))) (v := v)
have hn : node.val ≠ [] := by
intro hn
have hp := T.markingPlus_depth_pos node hnode
simp [UniformTree.depth, hn] at hp
have hcoord : (D).rowCoordinate
((D).stateMainRow v false (.inl (.inl (node, ⟨0, hd⟩)))) =
TreeGeometry.right G.edges.length R (D).geometryBound .plus node.val := by
change TreeGeometry.right G.edges.length R (D).geometryBound .plus node.val - 0 = _
exact sub_zero _
have hwidth : TreeGeometry.right G.edges.length R (D).geometryBound .plus node.val =
TreeGeometry.left G.edges.length R (D).geometryBound .plus node.val +
Geometry.lambda G.edges.length R (D).geometryBound (UniformTree.depth node) := by
rw [TreeGeometry.right, TreeGeometry.width_of_ne_nil _ _ _ hn]
rfl
unfold localCompletion
dsimp only [InventoryData.ofCompetingTrees] at *
rw [hcoord, hlocal, hwidth]
linarith
private theorem minusMarked_completion_le (v : G.Vertex) (node : T.minus.Node)
(hnode : node ∈ T.markingMinus) :
localCompletion G T hd R k v true (.inl (.inr (.inl (node, ⟨0, hd⟩)))) ≤
TreeGeometry.left G.edges.length R (D).geometryBound .minus node.val := by
have hlocal := LocalResourceAllocation.minusMarked_local_length G T hd R k v node hnode
have hglobal := (D).stateMainLength_nonneg true
(.inl (.inr (.inl (node, ⟨0, hd⟩)))) (v := v)
have hn : node.val ≠ [] := by
intro hn
have hp := T.markingMinus_depth_pos node hnode
simp [UniformTree.depth, hn] at hp
have hcoord : (D).rowCoordinate
((D).stateMainRow v true (.inl (.inr (.inl (node, ⟨0, hd⟩))))) =
TreeGeometry.right G.edges.length R (D).geometryBound .minus node.val := by
change TreeGeometry.right G.edges.length R (D).geometryBound .minus node.val - 0 = _
exact sub_zero _
have hwidth : TreeGeometry.right G.edges.length R (D).geometryBound .minus node.val =
TreeGeometry.left G.edges.length R (D).geometryBound .minus node.val +
Geometry.lambda G.edges.length R (D).geometryBound (UniformTree.depth node) := by
rw [TreeGeometry.right, TreeGeometry.width_of_ne_nil _ _ _ hn]
rfl
unfold localCompletion
dsimp only [InventoryData.ofCompetingTrees] at *
rw [hcoord, hlocal, hwidth]
linarith
private theorem plusMarked_coverage (v : G.Vertex) (leaf : (D).PlusLeaf) {a : ℚ}
(ha : a ∈ (D).testInterval (.inl leaf : (D).TestAt v)) :
d ≤ coverageCount (localCompletion G T hd R k v false) (D).mainBaseline a := by
classical
apply (T.plus_rich leaf.val leaf.property).trans
apply card_le_coverage (localCompletion G T hd R k v false) (D).mainBaseline a
(T.markingPlus.filter (fun node => UniformTree.ancestor node leaf.val))
(fun node => .inl (.inl (node, ⟨0, hd⟩)))
· intro x y hxy
exact congrArg Prod.fst (Sum.inl.inj (Sum.inl.inj hxy))
· intro node hnode
obtain ⟨hmark, hancestor⟩ := Finset.mem_filter.mp hnode
have he := TreeGeometry.prefix_endpoints G.edges.length R (D).geometryBound .plus
hancestor (TreeGeometry.boundedAddress_node leaf.val (D).plus_branch_le_geometryBound)
exact ⟨(plusMarked_completion_le G T hd R k v node hmark).trans (he.1.trans ha.1),
ha.2.trans_le he.2⟩
private theorem minusMarked_coverage (v : G.Vertex) (leaf : (D).MinusLeaf) {a : ℚ}
(ha : a ∈ (D).testInterval (.inr (.inl leaf) : (D).TestAt v)) :
d ≤ coverageCount (localCompletion G T hd R k v true) (D).mainBaseline a := by
classical
apply (T.minus_rich leaf.val leaf.property).trans
apply card_le_coverage (localCompletion G T hd R k v true) (D).mainBaseline a
(T.markingMinus.filter (fun node => UniformTree.ancestor node leaf.val))
(fun node => .inl (.inr (.inl (node, ⟨0, hd⟩))))
· intro x y hxy
exact congrArg Prod.fst (Sum.inl.inj (Sum.inr.inj (Sum.inl.inj hxy)))
· intro node hnode
obtain ⟨hmark, hancestor⟩ := Finset.mem_filter.mp hnode
have he := TreeGeometry.prefix_endpoints G.edges.length R (D).geometryBound .minus
hancestor (TreeGeometry.boundedAddress_node leaf.val (D).minus_branch_le_geometryBound)
exact ⟨(minusMarked_completion_le G T hd R k v node hmark).trans (he.1.trans ha.1),
ha.2.trans_le he.2⟩
private theorem shortJob_coverage (v : G.Vertex) (job : (D).IncidencePosition v) {a : ℚ}
(ha : a ∈ (D).testInterval (.inr (.inr job) : (D).TestAt v)) :
d ≤ coverageCount (localCompletion G T hd R k v false) (D).mainBaseline a := by
classical
have hc := card_le_coverage (localCompletion G T hd R k v false)
(D).mainBaseline a (Finset.univ : Finset (Fin d))
(fun j => .inr (job, j))
(by intro i j hij; exact congrArg Prod.snd (Sum.inr.inj hij)) (by
intro j _
have hl := (D).localLength_nonneg
(.inl (LocalResourceAllocation.localEquiv G T hd R k v false (.inr (job, j))))
change Geometry.baseline G.edges.length R ((D).incidencePosition job) -
Geometry.delta G.edges.length R (D).geometryBound (D).L - 0 -
(D).localLength (.inl (LocalResourceAllocation.localEquiv G T hd R k v false
(.inr (job, j)))) ≤ a ∧
a < Geometry.baseline G.edges.length R ((D).incidencePosition job)
change Geometry.baseline G.edges.length R ((D).incidencePosition job) -
Geometry.delta G.edges.length R (D).geometryBound (D).L ≤ a ∧
a < Geometry.baseline G.edges.length R ((D).incidencePosition job) at ha
exact ⟨by linarith [ha.1], ha.2⟩)
simpa only [Finset.card_univ, Fintype.card_fin] using hc
theorem localCompletion_coverage (v : G.Vertex) (selected : Bool)
(test : (D).TestAt v) (a : ℚ) (ha : a ∈ (D).testInterval test) :
d ≤ coverageCount (localCompletion G T hd R k v selected) (D).mainBaseline a := by
cases selected
· rcases test with leaf | leaf | job
· exact plusMarked_coverage G T hd R k v leaf ha
· apply fundedRoot_coverage G T hd R k v false
have hroot := nodeInterval_subset_root leaf.val G.edges.length R (D).geometryBound .minus
(D).minus_branch_le_geometryBound ha
norm_num [TreeGeometry.rootOffset] at hroot ⊢
exact hroot
· exact shortJob_coverage G T hd R k v job ha
· rcases test with leaf | leaf | job
· apply fundedRoot_coverage G T hd R k v true
have hroot := nodeInterval_subset_root leaf.val G.edges.length R (D).geometryBound .plus
(D).plus_branch_le_geometryBound ha
norm_num [TreeGeometry.rootOffset] at hroot ⊢
exact hroot
· exact minusMarked_coverage G T hd R k v leaf ha
· apply fundedRoot_coverage G T hd R k v true
have hj := Geometry.closedJobCell_bounds
(Geometry.jobTestInterval_subset_closedJobCell G.edges.length R (D).geometryBound
(D).L ((D).incidencePosition job) ha)
exact ⟨by dsimp; linarith [hj.1], hj.2⟩
theorem exists_anchorEquiv (v : G.Vertex) (selected : Bool) :
∃ e : (D).MBase v ≃ (D).MBase v, ∀ b,
(D).rowCoordinate ((D).stateMainRow v selected b) - (D).stateMainLength selected b -
(D).localLength (.inl (LocalResourceAllocation.localEquiv G T hd R k v selected b)) ≤
(D).deadline (e b) := by
exact (D).exists_deadline_matching T.plus_height T.minus_height T.height_pos v
(localCompletion G T hd R k v selected)
(localCompletion_le_baseline G T hd R k v selected)
(localCompletion_coverage G T hd R k v selected)
end BinPackingGap.LocalCompletionCoverage
end
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Inventory/PackingExclusions.lean =====
namespace OAI
noncomputable section
namespace BinPackingGap
def excludedPositions {T Pos : Type*} [Fintype Pos]
(selected : Finset T) (I : T → Pos → Prop) : Finset Pos := by
classical
exact Finset.univ.filter fun r => ∃ t ∈ selected, I t r
@[simp] theorem mem_excludedPositions {T Pos : Type*} [Fintype Pos]
(selected : Finset T) (I : T → Pos → Prop) {r : Pos} :
r ∈ excludedPositions selected I ↔ ∃ t ∈ selected, I t r := by
classical
simp [excludedPositions]
theorem excludedPositions_card_le {T Pos : Type*} [Fintype Pos]
(selected : Finset T) (I : T → Pos → Prop)
(hunique : ∀ t ∈ selected, ∀ r s, I t r → I t s → r = s) :
(excludedPositions selected I).card ≤ selected.card := by
classical
have witness (r : ↥(excludedPositions selected I)) : ∃ t ∈ selected, I t r :=
(mem_excludedPositions selected I).mp r.property
let f : ↥(excludedPositions selected I) → ↥selected := fun r =>
⟨(witness r).choose, (witness r).choose_spec.1⟩
have hf (r : ↥(excludedPositions selected I)) : I (f r) r :=
(witness r).choose_spec.2
have hinj : Function.Injective f := by
intro r s hrs
have ht : (f r : T) = (f s : T) := congrArg (fun t : ↥selected => (t : T)) hrs
apply Subtype.ext
apply hunique (f r) (f r).property r s (hf r)
rw [ht]
exact hf s
simpa only [Fintype.card_coe] using Fintype.card_le_of_injective f hinj
def excludedRepetitions {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) : Finset (Fin R) := by
classical
exact Finset.univ.filter fun j => (e, j) ∈ bad
def nonexcludedRepetitions {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) : Finset (Fin R) := by
classical
exact Finset.univ.filter fun j => (e, j) ∉ bad
@[simp] theorem mem_excludedRepetitions {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) {j : Fin R} :
j ∈ excludedRepetitions bad e ↔ (e, j) ∈ bad := by
classical
simp [excludedRepetitions]
@[simp] theorem mem_nonexcludedRepetitions {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) {j : Fin R} :
j ∈ nonexcludedRepetitions bad e ↔ (e, j) ∉ bad := by
classical
simp [nonexcludedRepetitions]
theorem excludedRepetitions_card_le {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) :
(excludedRepetitions bad e).card ≤ bad.card := by
classical
let f : ↥(excludedRepetitions bad e) → ↥bad := fun j =>
⟨(e, j), (mem_excludedRepetitions bad e).mp j.property⟩
have hinj : Function.Injective f := by
intro j k hjk
apply Subtype.ext
exact congrArg Prod.snd (congrArg (fun x : ↥bad => (x : E × Fin R)) hjk)
simpa only [Fintype.card_coe] using Fintype.card_le_of_injective f hinj
theorem excluded_nonexcluded_card {E : Type*} {R : ℕ}
(bad : Finset (E × Fin R)) (e : E) :
(excludedRepetitions bad e).card + (nonexcludedRepetitions bad e).card = R := by
classical
have hdis : Disjoint (excludedRepetitions bad e) (nonexcludedRepetitions bad e) := by
apply Finset.disjoint_left.mpr
intro j hj hk
exact ((mem_nonexcludedRepetitions bad e).mp hk)
((mem_excludedRepetitions bad e).mp hj)
have hunion : excludedRepetitions bad e ∪ nonexcludedRepetitions bad e = Finset.univ := by
ext j
by_cases hj : (e, j) ∈ bad <;> simp [hj]
calc
_ = (excludedRepetitions bad e ∪ nonexcludedRepetitions bad e).card :=
(Finset.card_union_of_disjoint hdis).symm
_ = R := by rw [hunion]; simp
theorem nonexcludedRepetitions_add_card_bound {E : Type*} {R P : ℕ}
(bad : Finset (E × Fin R)) (e : E) (hbad : bad.card ≤ P) :
R ≤ P + (nonexcludedRepetitions bad e).card := by
calc
R = (excludedRepetitions bad e).card + (nonexcludedRepetitions bad e).card :=
(excluded_nonexcluded_card bad e).symm
_ ≤ P + (nonexcludedRepetitions bad e).card :=
Nat.add_le_add_right ((excludedRepetitions_card_le bad e).trans hbad) _
theorem nonexcludedRepetitions_card_ge {E : Type*} {R P : ℕ}
(bad : Finset (E × Fin R)) (e : E) (hbad : bad.card ≤ P) :
R - P ≤ (nonexcludedRepetitions bad e).card := by
apply Nat.sub_le_iff_le_add.mpr
simpa only [Nat.add_comm] using nonexcludedRepetitions_add_card_bound bad e hbad
theorem nonexcludedRepetitions_card_ge_real {E : Type*} {R P : ℕ}
(bad : Finset (E × Fin R)) (e : E) (hbad : bad.card ≤ P) :
(R : ℝ) - P ≤ ((nonexcludedRepetitions bad e).card : ℝ) := by
have h : (R : ℝ) ≤ (P : ℝ) + ((nonexcludedRepetitions bad e).card : ℝ) := by
exact_mod_cast nonexcludedRepetitions_add_card_bound bad e hbad
apply sub_le_iff_le_add.mpr
simpa only [add_comm] using h
theorem nonexcludedRepetitions_card_ge_of_unique_hits {T E : Type*} [Fintype E]
{R P : ℕ} (selected : Finset T) (I : T → E × Fin R → Prop)
(hunique : ∀ t ∈ selected, ∀ r s, I t r → I t s → r = s)
(hselected : selected.card ≤ P) (e : E) :
R - P ≤ (nonexcludedRepetitions (excludedPositions selected I) e).card :=
nonexcludedRepetitions_card_ge _ e ((excludedPositions_card_le selected I hunique).trans hselected)
theorem nonexcludedRepetitions_card_ge_real_of_unique_hits {T E : Type*} [Fintype E]
{R P : ℕ} (selected : Finset T) (I : T → E × Fin R → Prop)
(hunique : ∀ t ∈ selected, ∀ r s, I t r → I t s → r = s)
(hselected : selected.card ≤ P) (e : E) :
(R : ℝ) - P ≤ ((nonexcludedRepetitions (excludedPositions selected I) e).card : ℝ) :=
nonexcludedRepetitions_card_ge_real _ e
((excludedPositions_card_le selected I hunique).trans hselected)
namespace PackingCounts
variable {D : InventoryData} {I : Instance} {b : ℕ}
def tupleHitsJob (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) (r : D.Position) : Prop :=
(tupleClosedInterval p e t ∩
Geometry.closedJobCell D.graph.edges.length D.R D.geometryBound D.L r).Nonempty
def excludedAt (p : Packing I b) (e : D.Item ≃ I.Item) (v : D.Vertex) :
Finset D.Position :=
excludedPositions (zeroPositiveTuples p e v) (tupleHitsJob p e)
theorem selected_hits_job_unique (p : Packing I b) (e : D.Item ≃ I.Item)
(hL : 1 ≤ D.L) (v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ zeroPositiveTuples p e v) {r s : D.Position}
(hr : tupleHitsJob p e t r) (hs : tupleHitsJob p e t s) : r = s :=
Geometry.closedJobCell_unique_of_short_interval hL
(selected_interval_length_first p e v t ht) hr hs
theorem excludedAt_card_le (p : Packing I b) (e : D.Item ≃ I.Item)
(hL : 1 ≤ D.L) (v : D.Vertex) : (excludedAt p e v).card ≤ D.P := by
apply (excludedPositions_card_le (zeroPositiveTuples p e v) (tupleHitsJob p e) ?_).trans
(zeroPositiveTuples_card_le p e v)
intro t ht r s hr hs
exact selected_hits_job_unique p e hL v t ht hr hs
def goodRepetitions (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (edge : D.Edge) : Finset (Fin D.R) :=
nonexcludedRepetitions (excludedAt p e v) edge
theorem goodRepetitions_card_ge (p : Packing I b) (e : D.Item ≃ I.Item)
(hL : 1 ≤ D.L) (v : D.Vertex) (edge : D.Edge) :
D.R - D.P ≤ (goodRepetitions p e v edge).card :=
nonexcludedRepetitions_card_ge _ edge (excludedAt_card_le p e hL v)
theorem goodRepetitions_card_ge_real (p : Packing I b) (e : D.Item ≃ I.Item)
(hL : 1 ≤ D.L) (v : D.Vertex) (edge : D.Edge) :
(D.R : ℝ) - D.P ≤ ((goodRepetitions p e v edge).card : ℝ) :=
nonexcludedRepetitions_card_ge_real _ edge (excludedAt_card_le p e hL v)
theorem covering_not_selected_of_nonexcluded (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) (hr : r ∉ excludedAt p e v)
(t : p.TableBin (subclass e))
(ht : t ∈ tupleCovering p e v
(Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r)) :
t ∉ zeroPositiveTuples p e v := by
intro hselected
apply hr
apply (mem_excludedPositions _ _).mpr
refine ⟨t, hselected, ?_⟩
obtain ⟨_, hlo, hhi⟩ := (mem_tupleCovering p e v _ t).mp ht
refine ⟨Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r,
⟨hlo, hhi.le⟩, ?_⟩
exact Geometry.jobInterior_mem_closedJobCell _ _ _ _ _
end PackingCounts
end BinPackingGap
end
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Trees/InventoryRowGeometry.lean =====
namespace OAI
namespace BinPackingGap.InventoryData
variable (D : InventoryData)
private theorem node_right_in_root {T : UniformTree} (v : T.Node)
(s : TreeGeometry.Side) (hT : T.branchBound ≤ D.geometryBound) :
TreeGeometry.rootOffset s ≤
TreeGeometry.right D.graph.edges.length D.R D.geometryBound s v.val ∧
TreeGeometry.right D.graph.edges.length D.R D.geometryBound s v.val ≤
TreeGeometry.rootOffset s + 1 := by
apply TreeGeometry.nodeCell_subset_root D.graph.edges.length D.R D.geometryBound s hT v
exact ⟨(TreeGeometry.left_lt_right _ _ _ _ _).le, le_rfl⟩
theorem rowBaseline_le_one_of_not_tm {v : D.Vertex} (r : D.RowAt v)
(hclass : D.rowSubclass r ≠ .tm) : D.rowBaseline r ≤ 1 := by
rcases r with t | ⟨short, j⟩
· rcases t with ⟨node, i⟩ | ⟨node, i⟩ | i
· have h := D.node_right_in_root node .plus D.plus_branch_le_geometryBound
simpa only [rowBaseline, treeBaseline, TreeGeometry.rootOffset, zero_add] using h.2
· exact (hclass rfl).elim
· exact le_rfl
· exact (Geometry.job_baseline_lt_one _ _ _).le
theorem rowBaseline_ge_four_of_tm {v : D.Vertex} (r : D.RowAt v)
(hclass : D.rowSubclass r = .tm) : 4 ≤ D.rowBaseline r := by
rcases r with t | ⟨short, j⟩
· rcases t with ⟨node, i⟩ | ⟨node, i⟩ | i
· cases hclass
· exact (D.node_right_in_root node .minus D.minus_branch_le_geometryBound).1
· cases hclass
· cases hclass
theorem rowShort_eq_false_of_tm {v : D.Vertex} (r : D.RowAt v)
(hclass : D.rowSubclass r = .tm) : D.rowShort r = false := by
rcases r with t | ⟨short, j⟩
· rfl
· cases hclass
theorem exists_jobCopy_of_rowShort {v : D.Vertex} (r : D.RowAt v)
(hshort : D.rowShort r = true) : ∃ j : D.JobCopy v, r = .inr (true, j) := by
rcases r with t | ⟨short, j⟩
· cases hshort
· change short = true at hshort
subst short
exact ⟨j, rfl⟩
theorem row_zero_resources_empty {v : D.Vertex} (r : D.RowAt v)
(hshort : D.rowShort r = false) :
completionInterval (D.rowBaseline r) (D.rowShort r) 0 0
(Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) = ∅ := by
rw [hshort]
exact completionInterval_long_zero_lengths _ _
theorem row_zero_resources_job {v : D.Vertex} (r : D.RowAt v)
(hshort : D.rowShort r = true) :
∃ j : D.JobCopy v, r = .inr (true, j) ∧
D.rowPosition r = some (D.jobPosition j) ∧
completionInterval (D.rowBaseline r) (D.rowShort r) 0 0
(Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) =
Geometry.jobTestInterval D.graph.edges.length D.R D.geometryBound D.L
(D.jobPosition j) := by
obtain ⟨j, rfl⟩ := D.exists_jobCopy_of_rowShort r hshort
refine ⟨j, rfl, rfl, ?_⟩
exact completion_job_interval _ _ _ _ _
theorem minus_row_completion_gt_one {v w : D.Vertex} (r : D.RowAt v)
(u : D.GlobalCopy) (l : D.LocalAt w) (hclass : D.rowSubclass r = .tm) :
1 < completion (D.rowBaseline r) (D.rowShort r) (D.globalLength u)
(D.localLength l) (Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) := by
apply completion_minus_geometry_gt_one
D.graph.edges.length D.R D.geometryBound D.L
· exact D.rowBaseline_ge_four_of_tm r hclass
· exact D.rowShort_eq_false_of_tm r hclass
· exact D.globalLength_le_one u
· exact D.localLength_le_lambda_one l
theorem minus_row_not_cover_jobInterior {v w : D.Vertex} (r : D.RowAt v)
(u : D.GlobalCopy) (l : D.LocalAt w) (hclass : D.rowSubclass r = .tm)
(job : D.Position) :
Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L job ∉
completionInterval (D.rowBaseline r) (D.rowShort r) (D.globalLength u)
(D.localLength l) (Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) := by
intro hmem
have hh := D.minus_row_completion_gt_one r u l hclass
have hj := (Geometry.closedJobCell_bounds
(Geometry.jobInterior_mem_closedJobCell D.graph.edges.length D.R
D.geometryBound D.L job)).2
exact (not_le_of_gt (hj.trans hh)) hmem.1
theorem plus_row_not_cover_minus_side {v w : D.Vertex} (r : D.RowAt v)
(u : D.GlobalCopy) (l : D.LocalAt w) (hclass : D.rowSubclass r ≠ .tm)
{a : ℚ} (ha : 4 ≤ a) :
a ∉ completionInterval (D.rowBaseline r) (D.rowShort r) (D.globalLength u)
(D.localLength l) (Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) := by
apply not_mem_plus_completionInterval
· exact D.rowBaseline_le_one_of_not_tm r hclass
· linarith
end BinPackingGap.InventoryData
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Machines/PackingJobCoverage.lean =====
namespace OAI
noncomputable section
namespace BinPackingGap
namespace PackingCounts
variable {D : InventoryData} {I : Instance} {b : ℕ}
def shortMainAt (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) : Finset (p.TableBin (subclass e)) := by
classical
exact (Coverage.mainTuplesAt p (subclass e) (label e) v).filter fun t =>
tupleBaseline p e t = Geometry.baseline D.graph.edges.length D.R r ∧
tupleShort p e t = true
theorem main_unit_species (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ Coverage.mainTuplesAt p (subclass e) (label e) v)
(hu : D.globalUnit (globalCopy p e t) = true) :
(globalCopy p e t).1 = .up true ∨ (globalCopy p e t).1 = .um true := by
rcases hcopy : globalCopy p e t with ⟨s, i⟩
rw [hcopy] at hu
change s = .up true ∨ s = .um true
cases s with
| up one =>
change one = true at hu
exact Or.inl (congrArg GlobalSpecies.up hu)
| um one =>
change one = true at hu
exact Or.inr (congrArg GlobalSpecies.um hu)
| edge edge permit =>
have hglobal := roleCopy_subclass p e t .«global»
change D.itemSubclass ⟨.«global», globalCopy p e t⟩ = _ at hglobal
rw [hcopy] at hglobal
have hmain := ((Coverage.mem_mainTuplesAt p (subclass e) (label e) v t).mp ht).2.2
exfalso
apply hmain
cases hpattern : p.tablePattern (subclass e) t <;>
rw [hpattern] at hglobal <;> cases hglobal
theorem row_minus_of_global_um (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) (hu : (globalCopy p e t).1 = .um true) :
D.rowSubclass (rowCopy p e t).2 = .tm := by
have hg := roleCopy_subclass p e t .«global»
have hx := roleCopy_subclass p e t .x
have hclass : D.itemSubclass ⟨.«global», globalCopy p e t⟩ = .um := by
rcases hcopy : globalCopy p e t with ⟨s, i⟩
have hs : s = .um true := by simpa only [hcopy] using hu
subst s
rfl
have hpat : p.tablePattern (subclass e) t = .minusTree := by
rw [hclass] at hg
cases hp : p.tablePattern (subclass e) t <;> simp_all [patternSubclass]
rw [hpat] at hx
change D.itemSubclass ⟨.x, rowCopy p e t⟩ = .tm at hx
rcases hc : rowCopy p e t with ⟨w, r⟩
rw [hc] at hx
exact hx
theorem job_covering_global_not_um (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) (t : p.TableBin (subclass e))
(ht : t ∈ tupleCovering p e v
(Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r)) :
(globalCopy p e t).1 ≠ .um true := by
intro hu
have hrow := row_minus_of_global_um p e t hu
apply D.minus_row_not_cover_jobInterior (rowCopy p e t).2 (globalCopy p e t)
(localCopy p e t).2 hrow r
exact ((mem_tupleCovering p e v _ t).mp ht).2
theorem zero_resources_job_cover (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) (t : p.TableBin (subclass e))
(ht : t ∈ tupleCovering p e v
(Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r))
(hg : tupleGlobalLength p e t = 0) (hl : tupleLocalLength p e t = 0) :
tupleBaseline p e t = Geometry.baseline D.graph.edges.length D.R r ∧
tupleShort p e t = true := by
have hmem := ((mem_tupleCovering p e v _ t).mp ht).2
have hshort : tupleShort p e t = true := by
cases hs : tupleShort p e t with
| false =>
have hfinish : tupleFinish p e t = tupleBaseline p e t := by
simp [tupleFinish, hs, hg, hl]
rw [hfinish] at hmem
exact (not_lt_of_ge hmem.1 hmem.2).elim
| true => rfl
obtain ⟨j, hj, _, hinter⟩ := D.row_zero_resources_job (rowCopy p e t).2 hshort
have hmem' : Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r ∈
completionInterval (D.rowBaseline (rowCopy p e t).2)
(D.rowShort (rowCopy p e t).2) 0 0
(Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) := by
change completion _ _ 0 0 _ ≤ _ ∧ _ < _
simpa only [tupleFinish, hg, hl, tupleBaseline, tupleShort] using hmem
rw [hinter] at hmem'
have hpos : D.jobPosition j = r :=
(Geometry.jobInterior_mem_jobTestInterval_iff D.geometryBound D.L).mp hmem'
refine ⟨?_, hshort⟩
simp only [tupleBaseline, hj, InventoryData.rowBaseline, hpos]
theorem nonexcluded_covering_subset (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) (hr : r ∉ excludedAt p e v) :
tupleCovering p e v (Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r) ⊆
fundedTuples p e (.up true) v ∪ shortMainAt p e v r := by
classical
intro t ht
have hM := ((mem_tupleCovering p e v _ t).mp ht).1
by_cases hu : D.globalUnit (globalCopy p e t) = true
· have hspec := main_unit_species p e v t hM hu
rcases hspec with hp | hm
· exact Finset.mem_union_left _ ((mem_fundedTuples p e (.up true) v t).mpr
⟨hM, (selected_global_resource_iff p e t (.up true)).mpr hp⟩)
· exact (job_covering_global_not_um p e v r t ht hm).elim
· have hfalse : D.globalUnit (globalCopy p e t) = false := Bool.eq_false_of_not_eq_true hu
have hnot := covering_not_selected_of_nonexcluded p e v r hr t ht
have hnotpos : p.itemAtRole (subclass e) t .«local» ∉ positiveLocalResources e v := by
intro hp
exact hnot ((mem_zeroPositiveTuples p e v t).mpr ⟨hM, hfalse, hp⟩)
have hlocal := tupleLocalLength_eq_zero_of_not_positive p e v t
(Coverage.mainTuplesAt_subset_good p (subclass e) (label e) v hM) hnotpos
have hz := zero_resources_job_cover p e v r t ht
(tupleGlobalLength_eq_of_unit_false p e t hfalse) hlocal
exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hM, hz⟩)
theorem nonexcluded_coverage_upper (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) (hr : r ∉ excludedAt p e v) :
(tupleCovering p e v
(Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L r)).card ≤
xplus p e v + (shortMainAt p e v r).card := by
calc
_ ≤ (fundedTuples p e (.up true) v ∪ shortMainAt p e v r).card :=
Finset.card_le_card (nonexcluded_covering_subset p e v r hr)
_ ≤ _ := Finset.card_union_le _ _
end PackingCounts
end BinPackingGap
end
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Configurations/CoverageSoundness.lean =====
namespace OAI
noncomputable section
namespace BinPackingGap
namespace InventoryCoverage
variable {D : InventoryData} {I : Instance} {b : ℕ}
theorem coveringTuplesAt_eq (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (a : ℚ) :
Coverage.coveringTuplesAt p (PackingCounts.subclass e) (PackingCounts.label e) v
(rowBaseline e) (PackingCounts.tupleFinish p e) a =
PackingCounts.tupleCovering p e v a := by
unfold Coverage.coveringTuplesAt PackingCounts.tupleCovering
apply Finset.filter_congr
intro t _
rw [rowBaseline_selected p e t]
rfl
theorem shortMainAt_eq (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (r : D.Position) :
Coverage.currentShortMainAt p (PackingCounts.subclass e) (PackingCounts.label e) v
(rowBaseline e) (rowShort e) (Geometry.baseline D.graph.edges.length D.R r) =
PackingCounts.shortMainAt p e v r := by
unfold Coverage.currentShortMainAt PackingCounts.shortMainAt
apply Finset.filter_congr
intro t _
rw [rowBaseline_selected p e t, rowShort_selected p e t]
rfl
end InventoryCoverage
namespace InventoryData
variable (D : InventoryData)
theorem test_coverage {b c : ℕ}
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (hk : D.k ≤ D.graph.n)
(p : Packing D.packingInstance b) (hb : b ≤ D.B + c)
(v : D.Vertex) (t : D.TestAt v) (a : ℚ) (ha : a ∈ D.testInterval t) :
D.d ≤ (PackingCounts.tupleCovering p D.itemEquiv v a).card + 6 * lossAllowance c := by
classical
have hbad := D.badAnchorsAt_card_le hk p hb v
have horder := PackingCounts.edge_selected_baseline_le p D.itemEquiv
D.packingInstance_size_eq v
have hle : ∀ u ∈ Coverage.mainTuplesAt p (PackingCounts.subclass D.itemEquiv) (PackingCounts.label D.itemEquiv) v,
PackingCounts.tupleFinish p D.itemEquiv u ≤
InventoryCoverage.rowBaseline D.itemEquiv (p.itemAtRole (PackingCounts.subclass D.itemEquiv) u .x) := by
intro u _
simpa only [InventoryCoverage.rowBaseline_selected, PackingCounts.tupleBaseline] using
PackingCounts.tupleFinish_le_baseline p D.itemEquiv u
have hfeasible := PackingCounts.main_completion_le_selected_deadline p D.itemEquiv
D.packingInstance_size_eq v
have hdeficit := InventoryCoverage.actual_deadline_deficit_bound p D.itemEquiv v a
(lossAllowance c) (PackingCounts.tupleFinish p D.itemEquiv) hbad horder hle hfeasible
rw [D.deadline_prefix_at_test hplusheight hminusheight hL v t a ha,
InventoryCoverage.coveringTuplesAt_eq] at hdeficit
change (InventoryCoverage.originalBaselinePrefix D v a).card + D.d ≤
(InventoryCoverage.originalBaselinePrefix D v a).card +
(PackingCounts.tupleCovering p D.itemEquiv v a).card + 6 * lossAllowance c at hdeficit
omega
def longMatchesAt {b : ℕ} (p : Packing D.packingInstance b)
(v : D.Vertex) (r : D.IncidencePosition v) : ℕ :=
(Coverage.currentLongEdgeAt p D.encodedSubclass D.encodedLabel v
(InventoryCoverage.rowBaseline D.itemEquiv) (InventoryCoverage.keyBaseline D.itemEquiv)
(InventoryCoverage.rowShort D.itemEquiv)
(Geometry.baseline D.graph.edges.length D.R (D.incidencePosition r))).card
theorem long_matches_at_nonexcluded {b c : ℕ}
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (hk : D.k ≤ D.graph.n)
(p : Packing D.packingInstance b) (hb : b ≤ D.B + c)
(v : D.Vertex) (r : D.IncidencePosition v)
(hr : D.incidencePosition r ∉ PackingCounts.excludedAt p D.itemEquiv v) :
D.d ≤ D.longMatchesAt p v r + PackingCounts.xplus p D.itemEquiv v + 9 * lossAllowance c := by
classical
let a := Geometry.jobInterior D.graph.edges.length D.R D.geometryBound D.L (D.incidencePosition r)
let finish := PackingCounts.tupleFinish p D.itemEquiv
have hbad := D.badAnchorsAt_card_le hk p hb v
have horder := PackingCounts.edge_selected_baseline_le p D.itemEquiv
D.packingInstance_size_eq v
have hle : ∀ u ∈ Coverage.mainTuplesAt p (PackingCounts.subclass D.itemEquiv) (PackingCounts.label D.itemEquiv) v,
finish u ≤ InventoryCoverage.rowBaseline D.itemEquiv
(p.itemAtRole (PackingCounts.subclass D.itemEquiv) u .x) := by
intro u _
simpa only [finish, InventoryCoverage.rowBaseline_selected, PackingCounts.tupleBaseline] using
PackingCounts.tupleFinish_le_baseline p D.itemEquiv u
have hfeasible := PackingCounts.main_completion_le_selected_deadline p D.itemEquiv
D.packingInstance_size_eq v
have hpartition := Coverage.completion_prefix_decomposition p (PackingCounts.subclass D.itemEquiv)
(PackingCounts.label D.itemEquiv) v (InventoryCoverage.rowBaseline D.itemEquiv) finish hle a
have hdeadline := Coverage.deadline_prefix_le_completion_add_loss p (PackingCounts.subclass D.itemEquiv)
(PackingCounts.label D.itemEquiv) v (InventoryCoverage.anchorDeadline D.itemEquiv) finish a
(lossAllowance c) hbad hfeasible
have ha : a ∈ D.testInterval (.inr (.inr r) : D.TestAt v) :=
Geometry.jobInterior_mem_jobTestInterval D.graph.edges.length D.R D.geometryBound D.L
(D.incidencePosition r)
rw [InventoryCoverage.deadlinePrefix_card,
D.deadline_prefix_at_test hplusheight hminusheight hL v (.inr (.inr r)) a ha] at hdeadline
have hbase := InventoryCoverage.actual_displaced_job_prefix_le p D.itemEquiv v r
(lossAllowance c) hbad horder
have hupper : (Coverage.coveringTuplesAt p (PackingCounts.subclass D.itemEquiv) (PackingCounts.label D.itemEquiv) v
(InventoryCoverage.rowBaseline D.itemEquiv) finish a).card ≤
PackingCounts.xplus p D.itemEquiv v +
(Coverage.currentShortMainAt p (PackingCounts.subclass D.itemEquiv) (PackingCounts.label D.itemEquiv) v
(InventoryCoverage.rowBaseline D.itemEquiv) (InventoryCoverage.rowShort D.itemEquiv)
(Geometry.baseline D.graph.edges.length D.R (D.incidencePosition r))).card := by
simpa only [finish, a, InventoryCoverage.coveringTuplesAt_eq,
InventoryCoverage.shortMainAt_eq] using
PackingCounts.nonexcluded_coverage_upper p D.itemEquiv v (D.incidencePosition r) hr
have hcorrection := CoverageCounts.displaced_short_correction hpartition hdeadline hbase hupper
exact InventoryCoverage.actual_current_long_matches_from_correction p D.itemEquiv v r
(lossAllowance c) (PackingCounts.xplus p D.itemEquiv v) hbad horder hcorrection
end InventoryData
end BinPackingGap
end
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Trees/TreeAvoidance.lean =====
namespace OAI
namespace BinPackingGap
def pullMarks (stem : List ℕ) (marks : Finset (List ℕ)) : Finset (List ℕ) :=
(marks.filter (fun w => stem.IsPrefix w)).image (fun w => w.drop stem.length)
@[simp] theorem mem_pullMarks (stem word : List ℕ) (marks : Finset (List ℕ)) :
word ∈ pullMarks stem marks ↔ stem ++ word ∈ marks := by
constructor
· intro hw
obtain ⟨v, hv, hdrop⟩ := Finset.mem_image.mp hw
obtain ⟨hvA, hpref⟩ := Finset.mem_filter.mp hv
have heq : stem ++ word = v := by
calc
stem ++ word = stem ++ v.drop stem.length :=
congrArg (fun t => stem ++ t) hdrop.symm
_ = v.take stem.length ++ v.drop stem.length :=
congrArg (fun t => t ++ v.drop stem.length) (List.prefix_iff_eq_take.mp hpref)
_ = v := List.take_append_drop stem.length v
exact heq.symm ▸ hvA
· intro hw
exact Finset.mem_image.mpr
⟨stem ++ word, Finset.mem_filter.mpr ⟨hw, List.prefix_append stem word⟩,
by simp⟩
@[simp] theorem nil_mem_pullMarks (stem : List ℕ) (marks : Finset (List ℕ)) :
[] ∈ pullMarks stem marks ↔ stem ∈ marks := by
simpa only [List.append_nil] using mem_pullMarks stem [] marks
theorem levelCount_pullMarks_le (stem : List ℕ) (marks : Finset (List ℕ)) (j : ℕ) :
levelCount (pullMarks stem marks) j ≤ levelCount marks (stem.length + j) := by
have hsub : (pullMarks stem marks).filter (fun w => w.length = j) ⊆
(marks.filter (fun w => w.length = stem.length + j)).image
(fun w => w.drop stem.length) := by
intro w hw
obtain ⟨hw, hlen⟩ := Finset.mem_filter.mp hw
refine Finset.mem_image.mpr ⟨stem ++ w, ?_, by simp⟩
exact Finset.mem_filter.mpr
⟨(mem_pullMarks stem w marks).mp hw, by simp only [List.length_append, hlen]⟩
exact (Finset.card_le_card hsub).trans (Finset.card_image_le)
theorem disjoint_prefixes_append_of_pull (stem word : List ℕ)
(marks : Finset (List ℕ))
(hold : Disjoint marks (UniformTree.prefixes stem))
(hnew : Disjoint (pullMarks stem marks) (UniformTree.prefixes word)) :
Disjoint marks (UniformTree.prefixes (stem ++ word)) := by
apply Finset.disjoint_left.mpr
intro v hv hprefix
rw [prefixes_append_eq] at hprefix
rcases Finset.mem_union.mp hprefix with hprefix | hprefix
· exact Finset.disjoint_left.mp hold hv hprefix
· obtain ⟨w, _, hw, heq⟩ := mem_prefixesAfter_iff.mp hprefix
apply Finset.disjoint_left.mp hnew
· exact (mem_pullMarks stem w marks).mpr (heq.symm ▸ hv)
· exact UniformTree.mem_prefixes_iff.mpr hw
def extendPhaseQuota (height : ℕ) (old : ℕ → ℕ) (depth : ℕ) : ℕ :=
if depth ≤ height then old depth else phaseQuota (depth - height)
theorem extendPhaseQuota_old (height : ℕ) (old : ℕ → ℕ) {depth : ℕ}
(hdepth : depth ≤ height) : extendPhaseQuota height old depth = old depth := by
simp only [extendPhaseQuota, ite_eq_left hdepth]
theorem extendPhaseQuota_new (height : ℕ) (old : ℕ → ℕ) {j : ℕ}
(hj : 0 < j) : extendPhaseQuota height old (height + j) = phaseQuota j := by
have hnot : ¬ height + j ≤ height := by omega
simp only [extendPhaseQuota, ite_eq_right hnot, Nat.add_sub_cancel_left]
theorem graft_avoids {n : ℕ} (old : AuxiliaryTree n)
(G : old.tree.leaves → AuxiliaryTree 1) (N : ℕ)
(hG : ∀ l, (G l).tree.height = N)
(hquota : ∀ l, (G l).quota = phaseQuota)
(marks : Finset (List ℕ))
(hmarks : RespectsTreeQuota
(UniformTree.graft old.tree (fun l => (G l).tree) N hG)
(extendPhaseQuota old.tree.height old.quota) marks) :
∃ leaf ∈ (UniformTree.graft old.tree (fun l => (G l).tree) N hG).leaves,
Disjoint marks (UniformTree.prefixes leaf) := by
have hold : RespectsTreeQuota old.tree old.quota marks := by
refine ⟨hmarks.1, ?_⟩
intro j hj hbound
have hglobal := hmarks.2 j hj (by
change j ≤ old.tree.height + N
omega)
simpa only [extendPhaseQuota_old old.tree.height old.quota hbound] using hglobal
obtain ⟨l, hl, havoidOld⟩ := old.avoids marks hold
let oldLeaf : old.tree.leaves := ⟨l, hl⟩
have hlocal : RespectsTreeQuota (G oldLeaf).tree (G oldLeaf).quota
(pullMarks l marks) := by
constructor
· rw [nil_mem_pullMarks]
intro hmarked
exact Finset.disjoint_left.mp havoidOld hmarked
(UniformTree.mem_prefixes_iff.mpr (List.prefix_refl l))
· intro j hj hbound
have hjpos : 0 < j := by omega
have hlocalBound : j ≤ N := by simpa only [hG oldLeaf] using hbound
have hglobal := hmarks.2 (old.tree.height + j) (by omega) (by
change old.tree.height + j ≤ old.tree.height + N
omega)
have hpull := levelCount_pullMarks_le l marks j
rw [old.tree.length_leaf l hl] at hpull
rw [hquota oldLeaf]
exact hpull.trans (by
simpa only [extendPhaseQuota_new old.tree.height old.quota hjpos] using hglobal)
obtain ⟨w, hw, havoidNew⟩ := (G oldLeaf).avoids (pullMarks l marks) hlocal
refine ⟨l ++ w, ?_, disjoint_prefixes_append_of_pull l w marks havoidOld havoidNew⟩
exact (UniformTree.mem_graft_leaves old.tree (fun l => (G l).tree) N hG).mpr
⟨oldLeaf, w, hw, rfl⟩
end BinPackingGap
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Packing/PhaseIteration.lean =====
namespace OAI
namespace BinPackingGap
namespace UniformTree
def leafRank (T : UniformTree) (l : T.leaves) : ℕ :=
((T.leaves.orderIsoOfFin rfl).symm l).val + 1
theorem leafRank_pos (T : UniformTree) (l : T.leaves) : 0 < T.leafRank l := by
unfold leafRank
omega
theorem one_le_leafRank (T : UniformTree) (l : T.leaves) : 1 ≤ T.leafRank l :=
T.leafRank_pos l
theorem leafRank_le (T : UniformTree) (l : T.leaves) : T.leafRank l ≤ T.leaves.card := by
have h := ((T.leaves.orderIsoOfFin rfl).symm l).isLt
unfold leafRank
omega
theorem leafRank_injective (T : UniformTree) : Function.Injective T.leafRank := by
intro l m h
apply (T.leaves.orderIsoOfFin rfl).symm.injective
apply Fin.ext
exact Nat.add_right_cancel h
theorem leaf_card_pos (T : UniformTree) : 0 < T.leaves.card :=
Finset.card_pos.mpr T.leaves_nonempty
def rankedGadget (T : UniformTree) (l : T.leaves) : AuxiliaryTree 1 :=
ForkGadget.auxiliary T.leaves.card (T.leafRank l)
(T.one_le_leafRank l) (T.leafRank_le l)
@[simp] theorem rankedGadget_height (T : UniformTree) (l : T.leaves) :
(T.rankedGadget l).tree.height = T.leaves.card := rfl
@[simp] theorem rankedGadget_quota (T : UniformTree) (l : T.leaves) :
(T.rankedGadget l).quota = phaseQuota := rfl
theorem rankedGadget_red_depth (T : UniformTree) (l : T.leaves)
{w : List ℕ} (hw : w ∈ (T.rankedGadget l).red) : w.length = T.leafRank l :=
ForkGadget.auxiliary_red_depth _ _ _ _ hw
theorem rankedGadget_blue_depth (T : UniformTree) (l : T.leaves)
{w : List ℕ} (hw : w ∈ (T.rankedGadget l).blue) : w.length = T.leafRank l :=
ForkGadget.auxiliary_blue_depth _ _ _ _ hw
@[simp] theorem rankedGadget_card_red (T : UniformTree) (l : T.leaves) :
(T.rankedGadget l).red.card = phaseQuota (T.leafRank l) :=
ForkGadget.auxiliary_card_red _ _ _ _
@[simp] theorem rankedGadget_card_blue (T : UniformTree) (l : T.leaves) :
(T.rankedGadget l).blue.card = phaseQuota (T.leafRank l) :=
ForkGadget.auxiliary_card_blue _ _ _ _
def nextPhase (T : UniformTree) : UniformTree :=
T.graft (fun l => (T.rankedGadget l).tree) T.leaves.card
(fun l => T.rankedGadget_height l)
@[simp] theorem nextPhase_height (T : UniformTree) :
T.nextPhase.height = T.height + T.leaves.card := rfl
theorem height_lt_nextPhase (T : UniformTree) : T.height < T.nextPhase.height := by
rw [nextPhase_height]
exact Nat.lt_add_of_pos_right T.leaf_card_pos
theorem mem_nextPhase_leaves (T : UniformTree) {x : List ℕ} :
x ∈ T.nextPhase.leaves ↔
∃ l : T.leaves, ∃ w ∈ (T.rankedGadget l).tree.leaves, x = l.val ++ w :=
T.mem_graft_leaves _ _ _
def singletonRoot : UniformTree where
height := 0
leaves := {[]}
leaves_nonempty := ⟨[], Finset.mem_singleton_self []⟩
length_leaf := by
intro l hl
have hl' : l = [] := Finset.mem_singleton.mp hl
simp only [hl', List.length_nil]
positive_labels := by
intro l hl a ha
have hl' : l = [] := Finset.mem_singleton.mp hl
simp only [hl', List.not_mem_nil] at ha
end UniformTree
namespace AuxiliaryTree
def initial : AuxiliaryTree 0 where
tree := UniformTree.singletonRoot
quota := fun _ => 0
quota_pos := by
intro depth hpos hle
change depth ≤ 0 at hle
omega
red := ∅
blue := ∅
red_subset := Finset.empty_subset _
blue_subset := Finset.empty_subset _
root_not_red := by simp
root_not_blue := by simp
red_blue_disjoint := by simp
red_level := by simp [levelCount]
blue_level := by simp [levelCount]
total_count := by simp [colorCount]
red_witness := ⟨[], Finset.mem_singleton_self [], by simp [colorCount]⟩
blue_witness := ⟨[], Finset.mem_singleton_self [], by simp [colorCount]⟩
avoids := by
intro marks hmarks
refine ⟨[], Finset.mem_singleton_self [], ?_⟩
apply Finset.disjoint_left.mpr
intro w hw hp
have heq : w = [] := by
simpa only [UniformTree.mem_prefixes_iff, List.prefix_nil] using hp
exact hmarks.1 (heq ▸ hw)
def step {n : ℕ} (old : AuxiliaryTree n) : AuxiliaryTree (n + 1) where
tree := old.tree.nextPhase
quota := extendPhaseQuota old.tree.height old.quota
quota_pos := by
intro depth hpos _
unfold extendPhaseQuota
split_ifs with hdepth
· exact old.quota_pos depth hpos hdepth
· exact phaseQuota_pos _
red := old.red ∪ old.tree.liftMarks (fun l => (old.tree.rankedGadget l).red)
blue := old.blue ∪ old.tree.liftMarks (fun l => (old.tree.rankedGadget l).blue)
red_subset := by
intro w hw
rcases Finset.mem_union.mp hw with hw | hw
· exact old.tree.vertices_subset_graft _ _ _ (old.red_subset hw)
· exact old.tree.liftMarks_subset_graft_vertices _ _ _ _
(fun l => (old.tree.rankedGadget l).red_subset) hw
blue_subset := by
intro w hw
rcases Finset.mem_union.mp hw with hw | hw
· exact old.tree.vertices_subset_graft _ _ _ (old.blue_subset hw)
· exact old.tree.liftMarks_subset_graft_vertices _ _ _ _
(fun l => (old.tree.rankedGadget l).blue_subset) hw
root_not_red := by
intro h
rcases Finset.mem_union.mp h with h | h
· exact old.root_not_red h
· exact old.tree.root_not_mem_lift _
(fun l => (old.tree.rankedGadget l).root_not_red) h
root_not_blue := by
intro h
rcases Finset.mem_union.mp h with h | h
· exact old.root_not_blue h
· exact old.tree.root_not_mem_lift _
(fun l => (old.tree.rankedGadget l).root_not_blue) h
red_blue_disjoint := by
apply Finset.disjoint_left.mpr
intro w hr hb
rcases Finset.mem_union.mp hr with hr | hr <;>
rcases Finset.mem_union.mp hb with hb | hb
· exact Finset.disjoint_left.mp old.red_blue_disjoint hr hb
· exact Finset.disjoint_left.mp
(old.tree.old_marks_disjoint_lift old.red _ old.red_subset
(fun l => (old.tree.rankedGadget l).root_not_blue)) hr hb
· exact Finset.disjoint_left.mp
(old.tree.old_marks_disjoint_lift old.blue _ old.blue_subset
(fun l => (old.tree.rankedGadget l).root_not_red)) hb hr
· exact Finset.disjoint_left.mp
(old.tree.liftMarks_disjoint _ _
(fun l => (old.tree.rankedGadget l).red_blue_disjoint)) hr hb
red_level := by
intro depth hpos _
simpa only [extendPhaseQuota] using
old.tree.levelCount_union_liftMarks_le old.red
(fun l => (old.tree.rankedGadget l).red)
old.red_subset (fun l => (old.tree.rankedGadget l).root_not_red)
old.tree.leafRank old.tree.leafRank_injective
(fun l _ hw => old.tree.rankedGadget_red_depth l hw)
(fun l => (old.tree.rankedGadget_card_red l).le)
old.quota old.red_level depth hpos
blue_level := by
intro depth hpos _
simpa only [extendPhaseQuota] using
old.tree.levelCount_union_liftMarks_le old.blue
(fun l => (old.tree.rankedGadget l).blue)
old.blue_subset (fun l => (old.tree.rankedGadget l).root_not_blue)
old.tree.leafRank old.tree.leafRank_injective
(fun l _ hw => old.tree.rankedGadget_blue_depth l hw)
(fun l => (old.tree.rankedGadget_card_blue l).le)
old.quota old.blue_level depth hpos
total_count := by
intro leaf hleaf
obtain ⟨l, w, hw, rfl⟩ := old.tree.mem_nextPhase_leaves.mp hleaf
rw [old.tree.colorCount_union_liftMarks old.red _ old.red_subset
(fun l => (old.tree.rankedGadget l).root_not_red),
old.tree.colorCount_union_liftMarks old.blue _ old.blue_subset
(fun l => (old.tree.rankedGadget l).root_not_blue)]
have hold := old.total_count l.val l.property
have hnew := (old.tree.rankedGadget l).total_count w hw
omega
red_witness := by
obtain ⟨l, hl, hold⟩ := old.red_witness
let leaf : old.tree.leaves := ⟨l, hl⟩
obtain ⟨w, hw, hnew⟩ := (old.tree.rankedGadget leaf).red_witness
refine ⟨l ++ w, old.tree.mem_nextPhase_leaves.mpr ⟨leaf, w, hw, rfl⟩, ?_⟩
change colorCount (old.red ∪ old.tree.liftMarks
(fun l => (old.tree.rankedGadget l).red)) (leaf.val ++ w) = n + 1
rw [old.tree.colorCount_union_liftMarks old.red _ old.red_subset
(fun l => (old.tree.rankedGadget l).root_not_red) leaf w]
exact congrArg₂ (· + ·) hold hnew
blue_witness := by
obtain ⟨l, hl, hold⟩ := old.blue_witness
let leaf : old.tree.leaves := ⟨l, hl⟩
obtain ⟨w, hw, hnew⟩ := (old.tree.rankedGadget leaf).blue_witness
refine ⟨l ++ w, old.tree.mem_nextPhase_leaves.mpr ⟨leaf, w, hw, rfl⟩, ?_⟩
change colorCount (old.blue ∪ old.tree.liftMarks
(fun l => (old.tree.rankedGadget l).blue)) (leaf.val ++ w) = n + 1
rw [old.tree.colorCount_union_liftMarks old.blue _ old.blue_subset
(fun l => (old.tree.rankedGadget l).root_not_blue) leaf w]
exact congrArg₂ (· + ·) hold hnew
avoids := graft_avoids old old.tree.rankedGadget old.tree.leaves.card
old.tree.rankedGadget_height old.tree.rankedGadget_quota
@[simp] theorem step_height {n : ℕ} (old : AuxiliaryTree n) :
old.step.tree.height = old.tree.height + old.tree.leaves.card := rfl
theorem height_lt_step {n : ℕ} (old : AuxiliaryTree n) :
old.tree.height < old.step.tree.height := old.tree.height_lt_nextPhase
end AuxiliaryTree
def buildAuxiliary : (n : ℕ) → AuxiliaryTree n
| 0 => AuxiliaryTree.initial
| n + 1 => (buildAuxiliary n).step
@[simp] theorem buildAuxiliary_zero : buildAuxiliary 0 = AuxiliaryTree.initial := rfl
@[simp] theorem buildAuxiliary_succ (n : ℕ) :
buildAuxiliary (n + 1) = (buildAuxiliary n).step := rfl
theorem phases_le_buildAuxiliary_height (n : ℕ) : n ≤ (buildAuxiliary n).tree.height := by
induction n with
| zero => exact Nat.zero_le _
| succ n ih =>
have h := (buildAuxiliary n).height_lt_step
change n + 1 ≤ (buildAuxiliary n).step.tree.height
omega
theorem buildAuxiliary_height_pos {n : ℕ} (hn : 0 < n) :
0 < (buildAuxiliary n).tree.height :=
lt_of_lt_of_le hn (phases_le_buildAuxiliary_height n)
end BinPackingGap
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Trees/CompetingTrees.lean =====
namespace OAI
namespace BinPackingGap
def competingTrees (d : ℕ) (hd : 0 < d) : CompetingTrees d :=
CompetingTrees.ofAuxiliary d hd (buildAuxiliary (2 * d - 1))
theorem exists_competingTrees (d : ℕ) (hd : 0 < d) : Nonempty (CompetingTrees d) :=
⟨competingTrees d hd⟩
end BinPackingGap
end OAI
-- ===== Adapted from lean/OAI/Computability/BinPacking/Packing/ExtractedCover.lean =====
namespace OAI
noncomputable section
namespace BinPackingGap.SideChoice
open UniformTree
variable {α β : Type*} [DecidableEq α] [DecidableEq β]
omit [DecidableEq α] [DecidableEq β] in
theorem card_le_of_unique_hit [DecidableEq α] [DecidableEq β]
(tuples : Finset α) (nodes : Finset β)
(hits : α → β → Prop)
(hcover : ∀ v ∈ nodes, ∃ t ∈ tuples, hits t v)
(hunique : ∀ t ∈ tuples, ∀ v w, hits t v → hits t w → v = w) :
nodes.card ≤ tuples.card := by
classical
let f : nodes → tuples := fun v =>
⟨Classical.choose (hcover v.val v.property),
(Classical.choose_spec (hcover v.val v.property)).1⟩
have hf : ∀ v : nodes, hits (f v).val v.val := fun v =>
(Classical.choose_spec (hcover v.val v.property)).2
apply Finset.card_le_card_of_injective (f := f)
intro v w hvw
apply Subtype.ext
have ht : (f v).val = (f w).val := congrArg Subtype.val hvw
apply hunique (f v).val (f v).property v.val w.val (hf v)
rw [ht]
exact hf w
omit [DecidableEq α] [DecidableEq β] in
theorem level_card_le_resources [DecidableEq α] [DecidableEq β]
(selected : Finset α) (level : α → ℕ)
(resource : α → β) (stock : Finset β) (ℓ q : ℕ)
(hmap : ∀ t ∈ selected, level t = ℓ → resource t ∈ stock)
(hinj : Set.InjOn resource (selected.filter fun t => level t = ℓ))
(hstock : stock.card ≤ q) :
(selected.filter fun t => level t = ℓ).card ≤ q := by
apply (Finset.card_le_card_of_injOn resource ?_ hinj).trans hstock
intro t ht
exact hmap t (Finset.mem_filter.mp ht).1 (Finset.mem_filter.mp ht).2
variable {d : ℕ} (T : CompetingTrees d)
def taggedDepth : T.plus.Node ⊕ T.minus.Node → ℕ := Sum.elim depth depth
def marksPlus (selected : Finset α)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop) : Finset T.plus.Node := by
classical
exact Finset.univ.filter fun v => ∃ t ∈ selected, hits t (.inl v)
def marksMinus (selected : Finset α)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop) : Finset T.minus.Node := by
classical
exact Finset.univ.filter fun v => ∃ t ∈ selected, hits t (.inr v)
omit [DecidableEq α] in
@[simp] theorem mem_marksPlus [DecidableEq α] (selected : Finset α)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop) (v : T.plus.Node) :
v ∈ marksPlus T selected hits ↔ ∃ t ∈ selected, hits t (.inl v) := by
classical
simp [marksPlus]
omit [DecidableEq α] in
@[simp] theorem mem_marksMinus [DecidableEq α] (selected : Finset α)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop) (v : T.minus.Node) :
v ∈ marksMinus T selected hits ↔ ∃ t ∈ selected, hits t (.inr v) := by
classical
simp [marksMinus]
theorem roots_not_marked (selected : Finset α) (level : α → ℕ)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop)
(hpositive : ∀ t ∈ selected, 0 < level t)
(hdepth : ∀ t ∈ selected, ∀ v, hits t v → taggedDepth T v = level t) :
T.plus.root ∉ marksPlus T selected hits ∧
T.minus.root ∉ marksMinus T selected hits := by
constructor
· intro hroot
obtain ⟨t, ht, hhit⟩ := (mem_marksPlus T selected hits _).mp hroot
have hh : 0 = level t := hdepth t ht (.inl T.plus.root) hhit
have hp := hpositive t ht
omega
· intro hroot
obtain ⟨t, ht, hhit⟩ := (mem_marksMinus T selected hits _).mp hroot
have hh : 0 = level t := hdepth t ht (.inr T.minus.root) hhit
have hp := hpositive t ht
omega
theorem marked_level_card_le (selected : Finset α) (level : α → ℕ)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop)
(hdepth : ∀ t ∈ selected, ∀ v, hits t v → taggedDepth T v = level t)
(hunique : ∀ t ∈ selected, ∀ v w, hits t v → hits t w → v = w)
(ℓ : ℕ) :
((marksPlus T selected hits).filter fun v => depth v = ℓ).card +
((marksMinus T selected hits).filter fun v => depth v = ℓ).card ≤
(selected.filter fun t => level t = ℓ).card := by
classical
rw [← Finset.card_disjSum]
apply card_le_of_unique_hit _ _ hits
· intro v hv
cases v with
| inl v =>
have hv' := Finset.mem_filter.mp (Finset.inl_mem_disjSum.mp hv)
obtain ⟨t, ht, hhit⟩ := (mem_marksPlus T selected hits v).mp hv'.1
refine ⟨t, Finset.mem_filter.mpr ⟨ht, ?_⟩, hhit⟩
have hh : depth v = level t := hdepth t ht (.inl v) hhit
exact hh.symm.trans hv'.2
| inr v =>
have hv' := Finset.mem_filter.mp (Finset.inr_mem_disjSum.mp hv)
obtain ⟨t, ht, hhit⟩ := (mem_marksMinus T selected hits v).mp hv'.1
refine ⟨t, Finset.mem_filter.mpr ⟨ht, ?_⟩, hhit⟩
have hh : depth v = level t := hdepth t ht (.inr v) hhit
exact hh.symm.trans hv'.2
· intro t ht v w hv hw
exact hunique t (Finset.mem_filter.mp ht).1 v w hv hw
theorem exists_unhit_leaf (selected : Finset α) (level : α → ℕ)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop)
(hpositive : ∀ t ∈ selected, 0 < level t)
(hdepth : ∀ t ∈ selected, ∀ v, hits t v → taggedDepth T v = level t)
(hunique : ∀ t ∈ selected, ∀ v w, hits t v → hits t w → v = w)
(hstock : ∀ ℓ, 1 ≤ ℓ → ℓ ≤ T.height →
(selected.filter fun t => level t = ℓ).card ≤ T.quota ℓ) :
(∃ l : T.plus.Node, leaf l ∧
∀ t ∈ selected, ∀ v, hits t (.inl v) → ¬ ancestor v l) ∨
(∃ l : T.minus.Node, leaf l ∧
∀ t ∈ selected, ∀ v, hits t (.inr v) → ¬ ancestor v l) := by
have hroots := roots_not_marked T selected level hits hpositive hdepth
have hquota : ∀ ℓ, 1 ≤ ℓ → ℓ ≤ T.height →
((marksPlus T selected hits).filter fun v => depth v = ℓ).card +
((marksMinus T selected hits).filter fun v => depth v = ℓ).card ≤ T.quota ℓ := by
intro ℓ hlo hhi
exact (marked_level_card_le T selected level hits hdepth hunique ℓ).trans
(hstock ℓ hlo hhi)
rcases T.shared_obstruction (marksPlus T selected hits) (marksMinus T selected hits)
hroots.1 hroots.2 hquota with ⟨l, hl, havoid⟩ | ⟨l, hl, havoid⟩
· left
refine ⟨l, hl, ?_⟩
intro t ht v hhit
exact havoid v ((mem_marksPlus T selected hits v).mpr ⟨t, ht, hhit⟩)
· right
refine ⟨l, hl, ?_⟩
intro t ht v hhit
exact havoid v ((mem_marksMinus T selected hits v).mpr ⟨t, ht, hhit⟩)
theorem exists_leaf_coverage_le_funded (selected : Finset α) (level : α → ℕ)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop)
(fundPlus fundMinus : Finset α)
(coverPlus : T.plus.Node → Finset α) (coverMinus : T.minus.Node → Finset α)
(hpositive : ∀ t ∈ selected, 0 < level t)
(hdepth : ∀ t ∈ selected, ∀ v, hits t v → taggedDepth T v = level t)
(hunique : ∀ t ∈ selected, ∀ v w, hits t v → hits t w → v = w)
(hstock : ∀ ℓ, 1 ≤ ℓ → ℓ ≤ T.height →
(selected.filter fun t => level t = ℓ).card ≤ T.quota ℓ)
(hcoverPlus : ∀ l, leaf l → ∀ t ∈ coverPlus l,
t ∈ fundPlus ∨ t ∈ selected ∧ ∃ v, hits t (.inl v) ∧ ancestor v l)
(hcoverMinus : ∀ l, leaf l → ∀ t ∈ coverMinus l,
t ∈ fundMinus ∨ t ∈ selected ∧ ∃ v, hits t (.inr v) ∧ ancestor v l) :
(∃ l : T.plus.Node, leaf l ∧ (coverPlus l).card ≤ fundPlus.card) ∨
(∃ l : T.minus.Node, leaf l ∧ (coverMinus l).card ≤ fundMinus.card) := by
rcases exists_unhit_leaf T selected level hits hpositive hdepth hunique hstock with
⟨l, hl, havoid⟩ | ⟨l, hl, havoid⟩
· left
refine ⟨l, hl, Finset.card_le_card ?_⟩
intro t ht
rcases hcoverPlus l hl t ht with hfund | ⟨hselected, v, hhit, hancestor⟩
· exact hfund
· exact (havoid t hselected v hhit hancestor).elim
· right
refine ⟨l, hl, Finset.card_le_card ?_⟩
intro t ht
rcases hcoverMinus l hl t ht with hfund | ⟨hselected, v, hhit, hancestor⟩
· exact hfund
· exact (havoid t hselected v hhit hancestor).elim
theorem side_choice (selected : Finset α) (level : α → ℕ)
(hits : α → (T.plus.Node ⊕ T.minus.Node) → Prop)
(fundPlus fundMinus : Finset α)
(coverPlus : T.plus.Node → Finset α) (coverMinus : T.minus.Node → Finset α)
(K : ℕ)
(hpositive : ∀ t ∈ selected, 0 < level t)
(hdepth : ∀ t ∈ selected, ∀ v, hits t v → taggedDepth T v = level t)
(hunique : ∀ t ∈ selected, ∀ v w, hits t v → hits t w → v = w)
(hstock : ∀ ℓ, 1 ≤ ℓ → ℓ ≤ T.height →
(selected.filter fun t => level t = ℓ).card ≤ T.quota ℓ)
(hcoverPlus : ∀ l, leaf l → ∀ t ∈ coverPlus l,
t ∈ fundPlus ∨ t ∈ selected ∧ ∃ v, hits t (.inl v) ∧ ancestor v l)
(hcoverMinus : ∀ l, leaf l → ∀ t ∈ coverMinus l,
t ∈ fundMinus ∨ t ∈ selected ∧ ∃ v, hits t (.inr v) ∧ ancestor v l)
(hlowerPlus : ∀ l, leaf l → d ≤ (coverPlus l).card + 6 * K)
(hlowerMinus : ∀ l, leaf l → d ≤ (coverMinus l).card + 6 * K) :
d ≤ fundPlus.card + 6 * K ∨ d ≤ fundMinus.card + 6 * K := by
rcases exists_leaf_coverage_le_funded T selected level hits fundPlus fundMinus
coverPlus coverMinus hpositive hdepth hunique hstock hcoverPlus hcoverMinus with
⟨l, hl, hle⟩ | ⟨l, hl, hle⟩
· exact Or.inl ((hlowerPlus l hl).trans (Nat.add_le_add_right hle _))
· exact Or.inr ((hlowerMinus l hl).trans (Nat.add_le_add_right hle _))
end BinPackingGap.SideChoice
namespace BinPackingGap
section
def reductionTrees (c : ℕ) (ρ : ℝ) : CompetingTrees (depthDemand c ρ) :=
competingTrees (depthDemand c ρ) (depthDemand_pos c ρ)
def reductionInventory (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) : InventoryData :=
InventoryData.ofCompetingTrees G (reductionTrees c ρ)
(repetitions (reductionTrees c ρ).quotaTotal G.n (lossAllowance c)) k
def reductionInstance (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) : Instance :=
(reductionInventory c ρ G k).packingInstance
def reductionBinBound (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) : ℕ :=
(reductionInventory c ρ G k).B
@[simp] theorem reductionInventory_graph (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).graph = G := rfl
@[simp] theorem reductionInventory_d (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).d = depthDemand c ρ := rfl
@[simp] theorem reductionInventory_k (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).k = k := rfl
@[simp] theorem reductionInventory_P (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).P = (reductionTrees c ρ).quotaTotal := rfl
theorem reductionInventory_R (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).R =
repetitions (reductionInventory c ρ G k).P G.n (lossAllowance c) := rfl
theorem reductionInventory_R_pos (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
0 < (reductionInventory c ρ G k).R := repetitions_pos _ _ _
theorem reductionInventory_height_pos (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
0 < (reductionInventory c ρ G k).L := (reductionTrees c ρ).height_pos
theorem reductionInventory_plus_height (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).plus.height = (reductionInventory c ρ G k).L :=
(reductionTrees c ρ).plus_height
theorem reductionInventory_minus_height (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) :
(reductionInventory c ρ G k).minus.height = (reductionInventory c ρ G k).L :=
(reductionTrees c ρ).minus_height
theorem reductionInstance_count (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ)
(hk : k ≤ G.n) :
(reductionInstance c ρ G k).n = 5 * reductionBinBound c ρ G k :=
(reductionInventory c ρ G k).packingInstance_n hk
theorem reductionInstance_size_bounds (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ)
(i : (reductionInstance c ρ G k).Item) :
(1 / 6 : ℚ) < (reductionInstance c ρ G k).size i ∧
(reductionInstance c ρ G k).size i < 1 :=
(reductionInventory c ρ G k).packingInstance_size_mem_interval i
namespace PackingCounts
variable {D : InventoryData} {I : Instance} {b : ℕ}
private theorem selected_inventory_subclass (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) (r : Role) :
D.itemSubclass ⟨r, roleCopy p e t r⟩ =
patternSubclass (p.tablePattern (subclass e) t) r := by
have h := p.itemAtRole_subclass (subclass e) t r
rw [← roleCopy_item p e t r] at h
simpa only [subclass, Function.comp_apply, Equiv.symm_apply_apply] using h
private theorem selected_row_subclass (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) :
D.rowSubclass (rowCopy p e t).2 =
patternSubclass (p.tablePattern (subclass e) t) .x := by
have h := selected_inventory_subclass p e t .x
change D.itemSubclass ⟨.x, rowCopy p e t⟩ = _ at h
rcases hc : rowCopy p e t with ⟨v, r⟩
simpa only [hc, InventoryData.itemSubclass] using h
private theorem unit_global_species (u : D.GlobalCopy) (hu : D.globalUnit u = true) :
u.1 = .up true ∨ u.1 = .um true := by
rcases u with ⟨s, i⟩
cases s with
| up one => cases one <;> simp_all [InventoryData.globalUnit]
| um one => cases one <;> simp_all [InventoryData.globalUnit]
| edge edge permit => simp [InventoryData.globalUnit] at hu
private theorem selected_row_tm_of_um (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) {one : Bool}
(hs : (globalCopy p e t).1 = .um one) :
D.rowSubclass (rowCopy p e t).2 = .tm := by
have hg := selected_inventory_subclass p e t .«global»
have hclass : D.itemSubclass ⟨.«global», globalCopy p e t⟩ = .um := by
rcases hc : globalCopy p e t with ⟨s, i⟩
have hs' : s = .um one := by simpa only [hc] using hs
subst s
rfl
rw [hclass] at hg
have hx := selected_row_subclass p e t
cases hp : p.tablePattern (subclass e) t <;> simp_all [patternSubclass]
private theorem selected_row_not_tm_of_up (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) {one : Bool}
(hs : (globalCopy p e t).1 = .up one) :
D.rowSubclass (rowCopy p e t).2 ≠ .tm := by
have hg := selected_inventory_subclass p e t .«global»
have hclass : D.itemSubclass ⟨.«global», globalCopy p e t⟩ = .up := by
rcases hc : globalCopy p e t with ⟨s, i⟩
have hs' : s = .up one := by simpa only [hc] using hs
subst s
rfl
rw [hclass] at hg
have hx := selected_row_subclass p e t
cases hp : p.tablePattern (subclass e) t <;> simp_all [patternSubclass]
private theorem selected_global_resource (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) :
p.itemAtRole (subclass e) t .«global» ∈
globalResources e (globalCopy p e t).1 := by
apply (mem_globalResources e _ _).mpr
refine ⟨(globalCopy p e t).2, ?_⟩
exact roleCopy_item p e t .«global»
private theorem funded_of_species (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ Coverage.mainTuplesAt p (subclass e) (label e) v)
{s : GlobalSpecies D.graph} (hs : (globalCopy p e t).1 = s) :
t ∈ fundedTuples p e s v := by
apply (mem_fundedTuples p e s v t).mpr
refine ⟨ht, ?_⟩
have hr := selected_global_resource p e t
rwa [hs] at hr
theorem covering_plus_unit_funded (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ Coverage.mainTuplesAt p (subclass e) (label e) v)
(leaf : D.PlusLeaf) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .plus leaf.val)
(hu : D.globalUnit (globalCopy p e t) = true)
(hc : tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) :
t ∈ fundedTuples p e (.up true) v := by
rcases unit_global_species (globalCopy p e t) hu with hup | hum
· exact funded_of_species p e v t ht hup
· have hrow := selected_row_tm_of_um p e t hum
have hfinish : 1 < tupleFinish p e t :=
D.minus_row_completion_gt_one (rowCopy p e t).2 (globalCopy p e t)
(localCopy p e t).2 hrow
have hroot := TreeGeometry.nodeCell_subset_root D.graph.edges.length D.R
D.geometryBound .plus D.plus_branch_le_geometryBound leaf.val ha
have ha1 : a ≤ 1 := by
simpa only [TreeGeometry.rootOffset, zero_add] using hroot.2
exact False.elim (by linarith only [hfinish, ha1, hc.1])
theorem covering_minus_unit_funded (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ Coverage.mainTuplesAt p (subclass e) (label e) v)
(leaf : D.MinusLeaf) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .minus leaf.val)
(hu : D.globalUnit (globalCopy p e t) = true)
(hc : tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) :
t ∈ fundedTuples p e (.um true) v := by
rcases unit_global_species (globalCopy p e t) hu with hup | hum
· have hrow := selected_row_not_tm_of_up p e t hup
have hbase : tupleBaseline p e t ≤ 1 :=
D.rowBaseline_le_one_of_not_tm (rowCopy p e t).2 hrow
have hroot := TreeGeometry.nodeCell_subset_root D.graph.edges.length D.R
D.geometryBound .minus D.minus_branch_le_geometryBound leaf.val ha
have ha4 : 4 ≤ a := hroot.1
exact False.elim (by linarith only [hbase, ha4, hc.2])
· exact funded_of_species p e v t ht hum
theorem zero_lengths_cover_jobCell (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) {a : ℚ}
(hu : D.globalUnit (globalCopy p e t) = false)
(hl : tupleLocalLength p e t = 0)
(hc : tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) :
∃ j : D.JobCopy (rowCopy p e t).1,
a ∈ D.testCell (.inr (.inr j.1) : D.TestAt (rowCopy p e t).1) := by
have hg := tupleGlobalLength_eq_of_unit_false p e t hu
have hmem : a ∈ completionInterval (tupleBaseline p e t) (tupleShort p e t) 0 0
(Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) := by
change completion (tupleBaseline p e t) (tupleShort p e t) 0 0 _ ≤ a ∧
a < tupleBaseline p e t
simpa only [tupleFinish, hg, hl] using hc
change a ∈ completionInterval (D.rowBaseline (rowCopy p e t).2)
(D.rowShort (rowCopy p e t).2) 0 0
(Geometry.delta D.graph.edges.length D.R D.geometryBound D.L) at hmem
by_cases hs : D.rowShort (rowCopy p e t).2 = true
· obtain ⟨j, _, _, hj⟩ := D.row_zero_resources_job (rowCopy p e t).2 hs
rw [hj] at hmem
refine ⟨j, ?_⟩
change a ∈ Geometry.closedJobCell D.graph.edges.length D.R D.geometryBound D.L
(D.jobPosition j)
exact ⟨hmem.1, hmem.2.le⟩
· have hsfalse : D.rowShort (rowCopy p e t).2 = false := by
cases hh : D.rowShort (rowCopy p e t).2 <;> simp_all
rw [D.row_zero_resources_empty (rowCopy p e t).2 hsfalse] at hmem
cases hmem
theorem zero_lengths_not_cover_plus_leaf (p : Packing I b) (e : D.Item ≃ I.Item)
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (t : p.TableBin (subclass e)) (leaf : D.PlusLeaf) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .plus leaf.val)
(hu : D.globalUnit (globalCopy p e t) = false)
(hl : tupleLocalLength p e t = 0) :
¬ (tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) := by
intro hc
obtain ⟨j, hj⟩ := zero_lengths_cover_jobCell p e t hu hl hc
have hleaf : a ∈ D.testCell (.inl leaf : D.TestAt (rowCopy p e t).1) := ha
have hdis := D.testCell_disjoint hplusheight hminusheight hL
(show (.inl leaf : D.TestAt (rowCopy p e t).1) ≠ .inr (.inr j.1) by
intro h; cases h)
exact Set.disjoint_left.mp hdis hleaf hj
theorem zero_lengths_not_cover_minus_leaf (p : Packing I b) (e : D.Item ≃ I.Item)
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (t : p.TableBin (subclass e)) (leaf : D.MinusLeaf) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .minus leaf.val)
(hu : D.globalUnit (globalCopy p e t) = false)
(hl : tupleLocalLength p e t = 0) :
¬ (tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) := by
intro hc
obtain ⟨j, hj⟩ := zero_lengths_cover_jobCell p e t hu hl hc
have hleaf : a ∈ D.testCell (.inr (.inl leaf) : D.TestAt (rowCopy p e t).1) := ha
have hdis := D.testCell_disjoint hplusheight hminusheight hL
(show (.inr (.inl leaf) : D.TestAt (rowCopy p e t).1) ≠ .inr (.inr j.1) by
intro h; cases h)
exact Set.disjoint_left.mp hdis hleaf hj
end PackingCounts
open UniformTree
namespace InventoryData
variable (D : InventoryData)
def plusPoint (v : D.plus.Node) : ℚ :=
(TreeGeometry.left D.graph.edges.length D.R D.geometryBound .plus v.val +
TreeGeometry.right D.graph.edges.length D.R D.geometryBound .plus v.val) / 2
def minusPoint (v : D.minus.Node) : ℚ :=
(TreeGeometry.left D.graph.edges.length D.R D.geometryBound .minus v.val +
TreeGeometry.right D.graph.edges.length D.R D.geometryBound .minus v.val) / 2
theorem plusPoint_mem_Ico (v : D.plus.Node) :
D.plusPoint v ∈ Set.Ico
(TreeGeometry.left D.graph.edges.length D.R D.geometryBound .plus v.val)
(TreeGeometry.right D.graph.edges.length D.R D.geometryBound .plus v.val) := by
have h := TreeGeometry.left_lt_right D.graph.edges.length D.R D.geometryBound .plus v.val
dsimp only [plusPoint, Set.mem_Ico]
constructor <;> linarith
theorem minusPoint_mem_Ico (v : D.minus.Node) :
D.minusPoint v ∈ Set.Ico
(TreeGeometry.left D.graph.edges.length D.R D.geometryBound .minus v.val)
(TreeGeometry.right D.graph.edges.length D.R D.geometryBound .minus v.val) := by
have h := TreeGeometry.left_lt_right D.graph.edges.length D.R D.geometryBound .minus v.val
dsimp only [minusPoint, Set.mem_Ico]
constructor <;> linarith
theorem plusPoint_mem_cell (v : D.plus.Node) :
D.plusPoint v ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .plus v :=
⟨(D.plusPoint_mem_Ico v).1, (D.plusPoint_mem_Ico v).2.le⟩
theorem minusPoint_mem_cell (v : D.minus.Node) :
D.minusPoint v ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .minus v :=
⟨(D.minusPoint_mem_Ico v).1, (D.minusPoint_mem_Ico v).2.le⟩
def taggedAddress : D.plus.Node ⊕ D.minus.Node → TreeGeometry.Side × List ℕ
| .inl v => (.plus, v.val)
| .inr v => (.minus, v.val)
theorem taggedAddress_injective : Function.Injective D.taggedAddress := by
intro u v h
cases u with
| inl u =>
cases v with
| inl v => exact congrArg Sum.inl (Subtype.ext (congrArg Prod.snd h))
| inr v => have hs := congrArg Prod.fst h; cases hs
| inr u =>
cases v with
| inl v => have hs := congrArg Prod.fst h; cases hs
| inr v => exact congrArg Sum.inr (Subtype.ext (congrArg Prod.snd h))
def taggedNodeDepth (v : D.plus.Node ⊕ D.minus.Node) : ℕ :=
(D.taggedAddress v).2.length
def taggedNodeCell (v : D.plus.Node ⊕ D.minus.Node) : Set ℚ :=
TreeGeometry.cell D.graph.edges.length D.R D.geometryBound
(D.taggedAddress v).1 (D.taggedAddress v).2
theorem taggedAddress_bounded (v : D.plus.Node ⊕ D.minus.Node) :
TreeGeometry.BoundedAddress D.geometryBound (D.taggedAddress v).2 := by
cases v with
| inl v => exact TreeGeometry.boundedAddress_node v D.plus_branch_le_geometryBound
| inr v => exact TreeGeometry.boundedAddress_node v D.minus_branch_le_geometryBound
end InventoryData
namespace PackingCounts
variable {D : InventoryData} {I : Instance} {b : ℕ}
def tupleHits (p : Packing I b) (e : D.Item ≃ I.Item)
(t : p.TableBin (subclass e)) (v : D.plus.Node ⊕ D.minus.Node) : Prop :=
D.taggedNodeDepth v = tupleLocalDepth p e t ∧
(tupleClosedInterval p e t ∩ D.taggedNodeCell v).Nonempty
theorem selected_hits_unique (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ zeroPositiveTuples p e v)
(u w : D.plus.Node ⊕ D.minus.Node)
(hu : tupleHits p e t u) (hw : tupleHits p e t w) : u = w := by
apply D.taggedAddress_injective
exact TreeGeometry.eq_of_short_intersections D.graph.edges.length D.R D.geometryBound
(Finset.mem_Icc.mp (selected_depth_mem p e v t ht)).2
hu.1 hw.1 (D.taggedAddress_bounded u) (D.taggedAddress_bounded w)
(selected_interval_length p e v t ht) hu.2 hw.2
theorem main_local_nonzero_positive (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ Coverage.mainTuplesAt p (subclass e) (label e) v)
(hlocal : tupleLocalLength p e t ≠ 0) :
p.itemAtRole (subclass e) t .«local» ∈ positiveLocalResources e v := by
have hlabel := good_local_vertex p e v t
(Coverage.mainTuplesAt_subset_good p (subclass e) (label e) v ht)
cases hcopy : localCopy p e t with
| mk w l =>
have hwv : w = v := by simpa only [hcopy] using hlabel
subst w
rcases l with ((i | z) | j)
· apply (mem_positiveLocalResources e v _).mpr
refine ⟨i, ?_⟩
rw [← roleCopy_item p e t .«local»]
exact congrArg (fun x : (Σ w : D.Vertex, D.LocalAt w) => e ⟨.«local», x⟩)
hcopy.symm
· exact (hlocal (congrArg
(fun x : (Σ w : D.Vertex, D.LocalAt w) => D.localLength x.2) hcopy)).elim
· exact (hlocal (congrArg
(fun x : (Σ w : D.Vertex, D.LocalAt w) => D.localLength x.2) hcopy)).elim
theorem selected_hits_plus_ancestor (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ zeroPositiveTuples p e v) (hheight : D.plus.height = D.L)
(l : D.plus.Node) (hl : leaf l) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .plus l)
(hcover : tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) :
∃ u : D.plus.Node, tupleHits p e t (.inl u) ∧ ancestor u l := by
let ell := tupleLocalDepth p e t
have hell : ell ≤ depth l := by
rw [(leaf_iff_depth_eq_height l).mp hl, hheight]
exact (Finset.mem_Icc.mp (selected_depth_mem p e v t ht)).2
refine ⟨ancestorAt l ell, ⟨depth_ancestorAt l hell, ?_⟩, ancestorAt_ancestor l ell⟩
refine ⟨a, ⟨hcover.1, hcover.2.le⟩, ?_⟩
exact TreeGeometry.mem_ancestor_cell D.graph.edges.length D.R D.geometryBound .plus
D.plus_branch_le_geometryBound l ell ha
theorem selected_hits_minus_ancestor (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(ht : t ∈ zeroPositiveTuples p e v) (hheight : D.minus.height = D.L)
(l : D.minus.Node) (hl : leaf l) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .minus l)
(hcover : tupleFinish p e t ≤ a ∧ a < tupleBaseline p e t) :
∃ u : D.minus.Node, tupleHits p e t (.inr u) ∧ ancestor u l := by
let ell := tupleLocalDepth p e t
have hell : ell ≤ depth l := by
rw [(leaf_iff_depth_eq_height l).mp hl, hheight]
exact (Finset.mem_Icc.mp (selected_depth_mem p e v t ht)).2
refine ⟨ancestorAt l ell, ⟨depth_ancestorAt l hell, ?_⟩, ancestorAt_ancestor l ell⟩
refine ⟨a, ⟨hcover.1, hcover.2.le⟩, ?_⟩
exact TreeGeometry.mem_ancestor_cell D.graph.edges.length D.R D.geometryBound .minus
D.minus_branch_le_geometryBound l ell ha
theorem covering_plus_classification (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (l : D.plus.Node) (hl : leaf l) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .plus l)
(ht : t ∈ tupleCovering p e v a) :
t ∈ fundedTuples p e (.up true) v ∨
t ∈ zeroPositiveTuples p e v ∧
∃ u : D.plus.Node, tupleHits p e t (.inl u) ∧ ancestor u l := by
obtain ⟨hmain, hcover⟩ := (mem_tupleCovering p e v a t).mp ht
cases hu : D.globalUnit (globalCopy p e t) with
| false =>
have hlocal : tupleLocalLength p e t ≠ 0 := by
intro hz
exact zero_lengths_not_cover_plus_leaf p e hplusheight hminusheight hL t
⟨l, hl⟩ ha hu hz hcover
have hselected : t ∈ zeroPositiveTuples p e v :=
(mem_zeroPositiveTuples p e v t).mpr
⟨hmain, hu, main_local_nonzero_positive p e v t hmain hlocal⟩
exact Or.inr ⟨hselected,
selected_hits_plus_ancestor p e v t hselected hplusheight l hl ha hcover⟩
| true =>
exact Or.inl (covering_plus_unit_funded p e v t hmain ⟨l, hl⟩ ha hu hcover)
theorem covering_minus_classification (p : Packing I b) (e : D.Item ≃ I.Item)
(v : D.Vertex) (t : p.TableBin (subclass e))
(hplusheight : D.plus.height = D.L) (hminusheight : D.minus.height = D.L)
(hL : 1 ≤ D.L) (l : D.minus.Node) (hl : leaf l) {a : ℚ}
(ha : a ∈ TreeGeometry.nodeCell D.graph.edges.length D.R D.geometryBound .minus l)
(ht : t ∈ tupleCovering p e v a) :
t ∈ fundedTuples p e (.um true) v ∨
t ∈ zeroPositiveTuples p e v ∧
∃ u : D.minus.Node, tupleHits p e t (.inr u) ∧ ancestor u l := by
obtain ⟨hmain, hcover⟩ := (mem_tupleCovering p e v a t).mp ht
cases hu : D.globalUnit (globalCopy p e t) with
| false =>
have hlocal : tupleLocalLength p e t ≠ 0 := by
intro hz
exact zero_lengths_not_cover_minus_leaf p e hplusheight hminusheight hL t
⟨l, hl⟩ ha hu hz hcover
have hselected : t ∈ zeroPositiveTuples p e v :=
(mem_zeroPositiveTuples p e v t).mpr
⟨hmain, hu, main_local_nonzero_positive p e v t hmain hlocal⟩
exact Or.inr ⟨hselected,
selected_hits_minus_ancestor p e v t hselected hminusheight l hl ha hcover⟩
| true =>
exact Or.inl (covering_minus_unit_funded p e v t hmain ⟨l, hl⟩ ha hu hcover)
theorem side_choice_of_competingTrees (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) (p : Packing I b)
(e : (InventoryData.ofCompetingTrees G T R k).Item ≃ I.Item)
(v : G.Vertex) (K : ℕ)
(hlowerPlus : ∀ l : T.plus.Node, leaf l →
d ≤ (tupleCovering p e v ((InventoryData.ofCompetingTrees G T R k).plusPoint l)).card +
6 * K)
(hlowerMinus : ∀ l : T.minus.Node, leaf l →
d ≤ (tupleCovering p e v ((InventoryData.ofCompetingTrees G T R k).minusPoint l)).card +
6 * K) :
d ≤ xplus p e v + 6 * K ∨ d ≤ xminus p e v + 6 * K := by
classical
let D := InventoryData.ofCompetingTrees G T R k
change d ≤ (fundedTuples p e (.up true) v).card + 6 * K ∨
d ≤ (fundedTuples p e (.um true) v).card + 6 * K
apply SideChoice.side_choice T (zeroPositiveTuples p e v) (tupleLocalDepth p e)
(tupleHits p e) (fundedTuples p e (.up true) v) (fundedTuples p e (.um true) v)
(fun l => tupleCovering p e v (D.plusPoint l))
(fun l => tupleCovering p e v (D.minusPoint l)) K
· intro t ht
exact Nat.lt_of_lt_of_le Nat.zero_lt_one
(Finset.mem_Icc.mp (selected_depth_mem p e v t ht)).1
· intro t _ w hhit
cases w <;> exact hhit.1
· intro t ht u w hu hw
exact selected_hits_unique p e v t ht u w hu hw
· intro ell hlo hhi
exact zeroPositiveTuples_depth_card_le p e v
⟨ell, Finset.mem_Icc.mpr ⟨hlo, hhi⟩⟩
· intro l hl t ht
exact covering_plus_classification p e v t T.plus_height T.minus_height
(Nat.succ_le_of_lt T.height_pos) l hl (D.plusPoint_mem_cell l) ht
· intro l hl t ht
exact covering_minus_classification p e v t T.plus_height T.minus_height
(Nat.succ_le_of_lt T.height_pos) l hl (D.minusPoint_mem_cell l) ht
· exact hlowerPlus
· exact hlowerMinus
theorem side_choice_of_test_coverage (G : GraphInput) {d : ℕ}
(T : CompetingTrees d) (R k : ℕ) (p : Packing I b)
(e : (InventoryData.ofCompetingTrees G T R k).Item ≃ I.Item)
(v : G.Vertex) (K : ℕ)
(hcoverage : ∀ q : (InventoryData.ofCompetingTrees G T R k).TestAt v, ∀ a : ℚ,
a ∈ (InventoryData.ofCompetingTrees G T R k).testInterval q →
d ≤ (tupleCovering p e v a).card + 6 * K) :
d ≤ xplus p e v + 6 * K ∨ d ≤ xminus p e v + 6 * K := by
apply side_choice_of_competingTrees G T R k p e v K
· intro l hl
exact hcoverage (.inl ⟨l, hl⟩) _
((InventoryData.ofCompetingTrees G T R k).plusPoint_mem_Ico l)
· intro l hl
exact hcoverage (.inr (.inl ⟨l, hl⟩)) _
((InventoryData.ofCompetingTrees G T R k).minusPoint_mem_Ico l)
end PackingCounts
end
def extractedCover (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ) {b : ℕ}
(p : Packing (reductionInstance c ρ G k) b) : Finset G.Vertex :=
thresholdCover (depthDemand c ρ)
(PackingCounts.xplus p (reductionInventory c ρ G k).itemEquiv)
theorem reduction_side_choice (c : ℕ) (ρ : ℝ) (G : GraphInput) (k : ℕ)
(hk : k ≤ G.n) {b : ℕ} (p : Packing (reductionInstance c ρ G k) b)
(hb : b ≤ reductionBinBound c ρ G k + c) (v : G.Vertex) :
depthDemand c ρ ≤ PackingCounts.xplus p (reductionInventory c ρ G k).itemEquiv v +
6 * lossAllowance c ∨
depthDemand c ρ ≤ PackingCounts.xminus p (reductionInventory c ρ G k).itemEquiv v +
6 * lossAllowance c := by
let D := reductionInventory c ρ G k
apply PackingCounts.side_choice_of_test_coverage G (reductionTrees c ρ)
D.R k p D.itemEquiv v (lossAllowance c)
intro q a ha
exact D.test_coverage (reductionInventory_plus_height c ρ G k)
(reductionInventory_minus_height c ρ G k)
(Nat.succ_le_of_lt (reductionInventory_height_pos c ρ G k)) hk p hb v q a ha
theorem extractedCover_card_le (c : ℕ) (ρ : ℝ) (hρ : 0 < ρ)
(G : GraphInput) (k : ℕ) (hk : k ≤ G.n) {b : ℕ}
(p : Packing (reductionInstance c ρ G k) b)
(hb : b ≤ reductionBinBound c ρ G k + c) :
((extractedCover c ρ G k p).card : ℝ) ≤ (k : ℝ) + ρ * G.n := by
let D := reductionInventory c ρ G k
apply thresholdCover_card_le_graph G
(PackingCounts.xplus p D.itemEquiv) (PackingCounts.xminus p D.itemEquiv)
(depthDemand_pos c ρ) (depthDemand_ge_72 c ρ) hk hρ (depthDemand_ge_120_div c ρ)
· exact PackingCounts.xplus_budget p D.itemEquiv
· exact PackingCounts.total_budget p D.itemEquiv hk
· exact reduction_side_choice c ρ G k hk p hb
end BinPackingGap
end
end OAI