AFTD Auto-Formalizing Theoretical Domains

optimal_timely_bin_count

def

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 TimelyBin is a valid timely packing of an item set I : Finset TimelyItem, written…
  • TimelyBinA structure TimelyBin representing a bin in timely bin packing, with fields items : Finset TimelyItem (the finite set of items packed…
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…

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}
See it in the graphDiscuss this resultChallenge it