AFTD Auto-Formalizing Theoretical Domains

multidim_opt_nonneg

theoremverified

The offline optimal total completion time multidim_opt I of any multidimensional scheduling instance I with D resources is non-negative.

Statement

theorem multidim_opt_nonneg {D : ℕ} (I : MultidimInstance D) : 0 ≤ multidim_opt I
Source
folklore
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
  • multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
  • 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…

Read back from the Lean

For every natural number D and every multidimensional instance I of dimension D, the value multidim_opt I (the infimum of the sum of job completion times over all feasible schedules) is greater than or equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The offline optimal completion time is defined as the infimum of the set of total completion times of all feasible schedules. Every feasible schedule requires completion times to be non-negative, making every feasible total completion time non-negative. If feasible schedules exist, the infimum is bounded below by 0; if no feasible schedule exists, the infimum is 0 by Lean's convention for the infimum of the empty set.

  1. Every total completion time achieved by a feasible schedule is non-negative.

    By definition, multidim_opt is the infimum of the set $S$ of total completion times $\sum_{j} C_j$ for feasible schedules $(x, C)$. For any $s \in S$, feasibility requires each individual completion time to satisfy $0 \le C_j$. Since a finite sum of non-negative real numbers is non-negative (by `Finset.sum_nonneg`), every element $s \in S$ satisfies $0 \le s$.

    lines 3–10

    uses Finset.sum_nonneg

      dsimp [multidim_opt]
      have h_nonneg : ∀ s ∈ { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j }, 0 ≤ s := by
        intro s hs
        rcases hs with ⟨x, C, h_feas, rfl⟩
        rcases h_feas with ⟨-, -, hC⟩
        apply Finset.sum_nonneg
        intro j _
        exact (hC j).1
  2. If there is at least one feasible schedule, the optimal completion time is non-negative.

    We split into cases on whether the set $S$ of feasible completion times is non-empty. When $S$ is non-empty, $0$ is a lower bound for every element of $S$, so by `le_csInf`, the infimum satisfies $0 \le \inf S$.

    lines 11–12

    uses le_csInf

      by_cases hS : { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j }.Nonempty
      · exact le_csInf hS h_nonneg
  3. If there are no feasible schedules, the optimal completion time is also non-negative.

    If $S$ is not non-empty, it is the empty set (by `Set.not_nonempty_iff_eq_empty.mp`). In Lean's conditionally complete lattice on $\mathbb{R}$, the infimum of the empty set is defined to be $0$ (`Real.sInf_empty`). Substituting this yields $0 \le 0$, which holds by reflexivity.

    lines 13–15

    uses Set.not_nonempty_iff_eq_empty.mp, Real.sInf_empty

      · have : { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j } = ∅ :=
          Set.not_nonempty_iff_eq_empty.mp hS
        rw [this, Real.sInf_empty]
Finset.sum_nonneg
If every term in a finite sum is non-negative, the sum is non-negative.
le_csInf
For a non-empty set in a conditionally complete lattice, any lower bound is less than or equal to the infimum of the set.
Real.sInf_empty
The infimum of the empty set of real numbers is 0.
Set.not_nonempty_iff_eq_empty.mp
If a set is not non-empty, it is equal to the empty set.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The offline optimal total completion time of a multidimensional scheduling instance is non-negative. -/theorem multidim_opt_nonneg {D : ℕ} (I : MultidimInstance D) : 0 ≤ multidim_opt I := by  dsimp [multidim_opt]  have h_nonneg : ∀ s ∈ { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j }, 0 ≤ s := by    intro s hs    rcases hs with ⟨x, C, h_feas, rfl⟩    rcases h_feas with ⟨-, -, hC⟩    apply Finset.sum_nonneg    intro j _    exact (hC j).1  by_cases hS : { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j }.Nonempty  · exact le_csInf hS h_nonneg  · have : { s | ∃ (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ), multidim_is_feasible_schedule I x C ∧ s = ∑ j, C j } = ∅ :=      Set.not_nonempty_iff_eq_empty.mp hS    rw [this, Real.sInf_empty]
See it in the graphDiscuss this resultChallenge it