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
TimelyItemrepresenting an item in online timely bin packing, with fieldsid : ℕ(a unique natural identifier),… - timelyItemToTupleThe tuple representation
timelyItemToTuplemapping each timely itempto the lexicographically ordered tuple…
- TimelyItemA structure
- Used by 4
- thrifty_greedy_stepFor a non-empty set of remaining timely items
Rwith witnesshR : R.Nonempty,thrifty_greedy_step R hRreturns theTimelyBinwhose… - is_valid_timely_packingA finite set of bins
P : Finset TimelyBinis a valid timely packing of an item setI : Finset TimelyItem, written… - thrifty_greedy_auxA fuel-bounded recursive procedure
thrifty_greedy_aux : ℕ → Finset TimelyItem → Finset TimelyBinthat, on remaining itemsR, returns… - greedy_pack_listGiven a remaining capacity
remCap : ℝand a list of timely items,greedy_pack_list remCap : List TimelyItem → Finset TimelyItem…
- thrifty_greedy_stepFor a non-empty set of remaining timely items
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)