AFTD Auto-Formalizing Theoretical Domains

instLinearOrderTimelyItem

instance

The linear order on TimelyItem obtained by pulling back the lexicographic order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injective function timelyItemToTuple.

Statement

noncomputable instance instLinearOrderTimelyItem : LinearOrder TimelyItem
Defined in
arXiv:2611.09611, Section 1.1 and Section 2
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • TimelyItemA structure TimelyItem representing an item in online timely bin packing, with fields id : ℕ (a unique natural identifier),…
  • timelyItemToTupleThe tuple representation timelyItemToTuple mapping each timely item p to the lexicographically ordered tuple…
Used by 4
  • 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…
  • thrifty_greedy_auxA fuel-bounded recursive procedure thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBin that, on remaining items R, returns…
  • 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

A LinearOrder instance on TimelyItem, constructed by pulling back (via LinearOrder.lift') the lexicographic linear order on ℝ ×ₗ ℕ ×ₗ ℝ ×ₗ ℝ along the injection timelyItemToTuple, which maps each item p to (p.deadline, p.id, p.arrival, p.size). Under this order, p ≤ q if and only if (p.deadline, p.id, p.arrival, p.size) ≤ (q.deadline, q.id, q.arrival, q.size) in the lexicographical product order.

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

/-- Linear order on timely items prioritizing earliest deadline, breaking ties by item id, arrival, and size. -/
noncomputable instance instLinearOrderTimelyItem : LinearOrder TimelyItem := LinearOrder.lift' timelyItemToTuple (by intro ⟨i1, a1, d1, s1⟩ ⟨i2, a2, d2, s2⟩ h; cases h; rfl)
See it in the graphDiscuss this resultChallenge it