multidim_opt_nonneg
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.
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$.
uses
Finset.sum_nonnegdsimp [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
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$.
uses
le_csInfby_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
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.
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.
- In standard mathematics, the infimum of the empty set is $+\infty$ (or undefined). In Lean's ConditionallyCompleteLattice instance for $\mathbb{R}$, `sInf ∅` is defined by convention to be $0$ (`Real.sInf_empty`). The second case of the proof relies on this convention.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]