AFTD Auto-Formalizing Theoretical Domains

TimelyItem

structure

A structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier), arrival : ℝ (a real arrival time), deadline : ℝ (a real deadline), and size : ℝ (a real size).

Statement

structure TimelyItem
Defined in
arXiv:2611.09611, Section 1.1
Verified
09 Nov 2026
Axioms
none listed
Used by 12
  • thrifty_greedy_countThe number of bins thrifty_greedy_count I produced by Thrifty-Greedy on instance I : Finset TimelyItem, defined as the cardinality…
  • timelyItemToTuple_injectiveThe mapping timelyItemToTuple from timely items to lexicographically ordered tuples ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ is injective.
  • optimal_timely_bin_countThe optimal offline number of bins optimal_timely_bin_count I for an instance I : Finset TimelyItem is the infimum in ℕ of the…
  • thrifty_greedyThe Thrifty-Greedy packing thrifty_greedy I of an instance I : Finset TimelyItem, defined as thrifty_greedy_aux I.card I.
  • thrifty_greedy_stepFor a non-empty set of remaining timely items R with witness hR : R.Nonempty, thrifty_greedy_step R hR returns the TimelyBin whose…
  • 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…
  • thrifty_greedy_auxA fuel-bounded recursive procedure thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin that, on remaining items R, returns…
  • instLinearOrderTimelyItemThe linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function…
  • timelyItemToTupleThe tuple representation timelyItemToTuple mapping each timely item p to the lexicographically ordered tuple…
  • timely_bin_is_validA timely bin b : TimelyBin is valid, written timely_bin_is_valid b, if for every item p ∈ b.items the packing time b.time…
  • greedy_pack_listGiven a remaining capacity remCap : ℝ and a list of timely items, greedy_pack_list remCap : List TimelyItem → Finset TimelyItem…

Read back from the Lean

The definition of a structure TimelyItem with four fields: id of type ℕ (a natural number), and arrival, deadline, and size, each of type ℝ (real numbers).

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

/-- An item in online timely bin packing with an identifier, arrival time, deadline, and size. -/
structure TimelyItem where
  id : ℕ
  arrival : ℝ
  deadline : ℝ
  size : ℝ
See it in the graphDiscuss this resultChallenge it