AFTD Auto-Formalizing Theoretical Domains

thrifty_greedy_step

def

For a non-empty set of remaining timely items R with witness hR : R.Nonempty, thrifty_greedy_step R hR returns the TimelyBin whose trigger item is the minimal element p = R.min' hR under the linear order, whose packing time is p.deadline, and whose items consist of p together with the items from (R.erase p).filter (fun q => q.arrival ≤ p.deadline), sorted by (· ≤ ·), that fit into the remaining capacity 1 - p.size according to greedy_pack_list.

Statement

noncomputable def thrifty_greedy_step (R : Finset TimelyItem) (hR : R.Nonempty) : TimelyBin
Defined in
arXiv:2611.09611, Section 2
Verified
09 Nov 2026
Axioms
none listed
Built on 6
  • instLinearOrderTimelyItemThe linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function…
  • TimelyBinA structure TimelyBin representing a bin in timely bin packing, with fields items : Finset TimelyItem (the finite set of items packed…
  • greedy_pack_listGiven a remaining capacity remCap : ℝ and a list of timely items, greedy_pack_list remCap : List TimelyItem → Finset TimelyItem…
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • thrifty_greedy_auxA fuel-bounded recursive procedure thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin that, on remaining items R, returns…

Read back from the Lean

thrifty_greedy_step defines a function that takes: 1. R : Finset TimelyItem, a finite set of timely items (where each item has fields id : ℕ, arrival : ℝ, deadline : ℝ, and size : ℝ), and 2. hR : R.Nonempty, a proof that R is nonempty, and produces a TimelyBin (a structure with items : Finset TimelyItem and time : ℝ) constructed as follows: - Let p be the minimum element of R with respect to the ambient linear order on TimelyItem (R.min' hR). - Let t = p.deadline. - Let pending be the subset of R \ {p} consisting of all items q whose arrival time satisfies q.arrival ≤ t. - Sort pending in ascending order (using ≤) into a list pendingList. - Greedily pack items from pendingList into a bin of remaining capacity 1 - p.size via greedy_pack_list: traversing pendingList in order, an item x is included if its size is at most the remaining capacity, after which remaining capacity is decreased by x.size; otherwise x is skipped. Let others be the finite set of items selected by this procedure. - Return the TimelyBin with items equal to {p} ∪ others and time equal to t.

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

/-- One step of Thrifty-Greedy: open a bin for the earliest-deadline pending item and greedily fill it. -/
noncomputable def thrifty_greedy_step (R : Finset TimelyItem) (hR : R.Nonempty) : TimelyBin :=
  open Classical in
  let p := R.min' hR
  let t := p.deadline
  let pending := (R.erase p).filter (fun q => q.arrival ≤ t)
  let pendingList := pending.sort (· ≤ ·)
  let others := greedy_pack_list (1 - p.size) pendingList
  { items := insert p others, time := t }
See it in the graphDiscuss this resultChallenge it