AFTD Auto-Formalizing Theoretical Domains

MultidimInstance

structure

An instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with processing requirements p_j > 0, rate caps u_j > 0, and demand vectors a_j in [0, 1]^D such that each entry is in [0, 1] and at least one entry equals 1.

Statement

structure MultidimInstance (D : ℕ)
Defined in
arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Section 2.1
Verified
08 Nov 2026
Axioms
none listed
Used by 9
  • multidim_opt_nonnegThe offline optimal total completion time multidim_opt I of any multidimensional scheduling instance I with D resources is non-negative.
  • multidim_instance_existsFor every natural number D ≥ 1, there exists an instance of multidimensional scheduling with D resources.
  • drf_cap_lower_bound_le_optFor every multidimensional scheduling instance I with D resources and zero release times, the sum over all jobs of processing requirement…
  • multidim_is_feasible_scheduleA rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule I x C for an instance I with D resources if for…
  • multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
  • oneshot_drf_fair_share_rateFor a multidimensional scheduling instance I with D resources and an active set of jobs A, the common fair-share rate…
  • oneshot_drf_total_completion_timeThe total completion time oneshot_drf_total_completion_time I of one-shot DRF on an instance I with D resources is defined as the real…
  • is_oneshot_drf_scheduleA rate allocation x and completion time vector C satisfy is_oneshot_drf_schedule I x C for an instance I with D resources if…
  • oneshot_drf_rateFor a multidimensional scheduling instance I with D resources, an active set of jobs A, and a job j, the one-shot DRF rate…

Read back from the Lean

A structure parameterized by a natural number D, containing: 1. A natural number n, 2. A proof hn that 0 < n, 3. A function p : Fin n → ℝ, 4. A proof hp that for every j : Fin n, 0 < p j, 5. A function u : Fin n → ℝ, 6. A proof hu that for every j : Fin n, 0 < u j, 7. A function a : Fin n → Fin D → ℝ, 8. A proof ha_nonneg that for all j : Fin n and d : Fin D, 0 ≤ a j d, 9. A proof ha_le_one that for all j : Fin n and d : Fin D, a j d ≤ 1, 10. A proof ha_dominant that for every j : Fin n, there exists some d : Fin D such that a j d = 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

/-- An instance of multidimensional scheduling with D resources and zero release times. -/
structure MultidimInstance (D : ℕ) where
  n : ℕ
  hn : 0 < n
  p : Fin n → ℝ
  hp : ∀ j, 0 < p j
  u : Fin n → ℝ
  hu : ∀ j, 0 < u j
  a : Fin n → Fin D → ℝ
  ha_nonneg : ∀ j d, 0 ≤ a j d
  ha_le_one : ∀ j d, a j d ≤ 1
  ha_dominant : ∀ j, ∃ d, a j d = 1
See it in the graphDiscuss this resultChallenge it