optimal_timely_bin_count
The optimal offline number of bins optimal_timely_bin_count I for an instance I : Finset TimelyItem is the infimum in ℕ of the cardinality of P over all finite sets of bins P : Finset TimelyBin that form a valid timely packing of I.
Statement
noncomputable def optimal_timely_bin_count (I : Finset TimelyItem) : ℕ
- Defined in
- arXiv:2611.09611, Section 1.1
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 3
- is_valid_timely_packingA finite set of bins
P : Finset TimelyBinis a valid timely packing of an item setI : Finset TimelyItem, written… - TimelyBinA structure
TimelyBinrepresenting a bin in timely bin packing, with fieldsitems : Finset TimelyItem(the finite set of items packed… - TimelyItemA structure
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),…
- is_valid_timely_packingA finite set of bins
Read back from the Lean
optimal_timely_bin_count I is a noncomputable definition that takes a finite set of timely items I and returns a natural number, defined as the infimum (sInf) in ℕ of the set of all natural numbers n such that there exists a finite set P of timely bins (TimelyBin) satisfying:
1. P is a valid timely packing of I (is_valid_timely_packing I P), which means:
a. Every bin b ∈ P is valid (timely_bin_is_valid b) and has a nonempty item set (b.items.Nonempty),
b. For all pairs of distinct bins b₁, b₂ ∈ P (b₁ ≠ b₂), their item sets are disjoint (Disjoint b₁.items b₂.items),
c. The union of the item sets across all bins in P is exactly I (P.biUnion (fun b => b.items) = I),
2. and the cardinality of P is n (P.card = n).
Here, a timely bin b is valid (timely_bin_is_valid b) if:
- For every item p ∈ b.items, the bin dispatch time b.time lies in [p.arrival, p.deadline] (i.e., p.arrival ≤ b.time ∧ b.time ≤ p.deadline), and
- The sum of the sizes of the items in b.items is at most 1 ((∑ p ∈ b.items, p.size) ≤ 1).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The optimal offline number of bins for an instance I is the minimum cardinality of a valid packing. -/ noncomputable def optimal_timely_bin_count (I : Finset TimelyItem) : ℕ := sInf {n : ℕ | ∃ P : Finset TimelyBin, is_valid_timely_packing I P ∧ P.card = n}