Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unrelated-Machines Load-Balancing Model and Algorithm

Definition
pd_unrelated_machines

by wenxinzhang · Aug 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingload-balancingonline-algorithmsprimal-dualscheduling

This module formalizes the normalized online load-balancing problem on unrelated machines and the Buchbinder–Naor primal–dual algorithm for it.

A normalized instance has m≥1m\ge 1m≥1 machines, jobs 0,…,n−10,\dots,n-10,…,n−1 arriving in this order, and a nonnegative normalized load p~(i,j)\tilde p(i,j)p~​(i,j) for every job–machine pair; machine jjj is eligible for job iii exactly when p~(i,j)≤1\tilde p(i,j)\le 1p~​(i,j)≤1. The associated covering primal minimizes ∑jx(j)+∑iz(i)\sum_j x(j)+\sum_i z(i)∑j​x(j)+∑i​z(i) subject to

p~(i,j) x(j)+z(i)  ≥  1for every eligible pair (i,j),\tilde p(i,j)\,x(j)+z(i)\;\ge\;1 \qquad \text{for every eligible pair } (i,j),p~​(i,j)x(j)+z(i)≥1for every eligible pair (i,j),

and its packing dual maximizes ∑(i,j)y(i,j)\sum_{(i,j)} y(i,j)∑(i,j)​y(i,j) subject to ∑jy(i,j)≤1\sum_{j} y(i,j)\le 1∑j​y(i,j)≤1 for every job iii and ∑ip~(i,j) y(i,j)≤1\sum_{i} \tilde p(i,j)\,y(i,j)\le 1∑i​p~​(i,j)y(i,j)≤1 for every machine jjj. Prefix versions of the program keep only the constraints of the first kkk jobs.

The algorithm is given as an executable causal online process. It initializes every machine weight to x(j)=1/(2m)x(j)=1/(2m)x(j)=1/(2m); on arrival of job iii it declares failure if iii has no eligible machine or if some current weight exceeds 111; otherwise it assigns iii irrevocably to an eligible machine ℓ\ellℓ minimizing p~(i,ℓ) x(ℓ)\tilde p(i,\ell)\,x(\ell)p~​(i,ℓ)x(ℓ) (ties broken by machine order), sets z(i)=1−p~(i,ℓ) x(ℓ)z(i)=1-\tilde p(i,\ell)\,x(\ell)z(i)=1−p~​(i,ℓ)x(ℓ) and y(i,ℓ)=1y(i,\ell)=1y(i,ℓ)=1, and updates x(ℓ)←x(ℓ) (1+p~(i,ℓ)/2)x(\ell)\leftarrow x(\ell)\,\bigl(1+\tilde p(i,\ell)/2\bigr)x(ℓ)←x(ℓ)(1+p~​(i,ℓ)/2). Failure is absorbing. The module also defines the assigned normalized load of each machine after any prefix, the predicate that a feasible dual assigns unit mass to every job, and the explicit bound ln⁡(3m)/ln⁡(3/2)\ln(3m)/\ln(3/2)ln(3m)/ln(3/2) appearing in the guarantee.

These definitions are the shared vocabulary for every theorem of the mission: the feasibility and objective statements refer to the same finite-LP interface, and the algorithmic statements refer to the same causal process.

Formalization Note The doubling wrapper that guesses the optimal makespan is deliberately outside this module; the mission covers the normalized single phase. Eligible pairs form a subtype, so dual vectors have no entries at ineligible pairs, while the algorithm's sparse yyy-updates live in a rectangular array inside the state.

Definition code
import Definitions.Def_pd_finite_lp
import Definitions.Def_pd_online_trace
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Tactic.NormNum

open scoped BigOperators

namespace PrimalDual
namespace UnrelatedMachines

noncomputable section

/--
A normalized unrelated-machines load-balancing instance for the
Buchbinder--Naor primal--dual algorithm. Jobs arrive in the order
`0, ..., jobs - 1`; `load i j` is the normalized processing load of job `i`
on machine `j`. The assumption `machines_pos` records that the finite machine
set is nonempty.

The doubling wrapper that guesses the optimum is deliberately outside this
structure: this is the normalized single-phase load-balancing problem.
-/
structure Instance (jobs machines : ℕ) where
  machines_pos : 0 < machines
  load : Fin jobs → Fin machines → ℝ
  load_nonneg : ∀ i j, 0 ≤ load i j

namespace Instance

variable {jobs machines : ℕ}

/-- Machines eligible for job `i`, namely those with normalized load at most one. -/
def eligible (I : Instance jobs machines) (i : Fin jobs) : Finset (Fin machines) :=
  Finset.univ.filter fun j ↦ I.load i j ≤ 1

@[simp]
theorem mem_eligible_iff (I : Instance jobs machines) (i : Fin jobs) (j : Fin machines) :
    j ∈ I.eligible i ↔ I.load i j ≤ 1 := by
  simp [eligible]

/-- A covering constraint is an eligible job--machine pair. -/
abbrev EligiblePair (I : Instance jobs machines) :=
  {q : Fin jobs × Fin machines // q.2 ∈ I.eligible q.1}

/-- Eligible constraints belonging to jobs among the first `k` arrivals. -/
abbrev EligiblePairThrough (I : Instance jobs machines) (k : ℕ) :=
  {q : I.EligiblePair // q.1.1.1 < k}

/-- The primal variables are machine weights `x(j)` and job slacks `z(i)`. -/
abbrev PrimalVar (jobs machines : ℕ) := Sum (Fin machines) (Fin jobs)

/--
The exact finite covering/packing LP for unrelated-machines load balancing:

* the primal minimizes `sum_j x(j) + sum_i z(i)` subject to
  `load(i,j) * x(j) + z(i) >= 1` for every eligible pair;
* the dual maximizes the sum of `y(i,j)`, with one capacity constraint per
  job and one load constraint per machine.
-/
def lp (I : Instance jobs machines) :
    FinitePrimalDual (PrimalVar jobs machines) I.EligiblePair where
  coeff v q :=
    match v with
    | Sum.inl j => if j = q.1.2 then I.load q.1.1 j else 0
    | Sum.inr i => if i = q.1.1 then 1 else 0
  rhs _ := 1
  cost _ := 1

/-- The load-balancing LP is a covering-primal/packing-dual pair. -/
theorem lp_isCoveringPacking (I : Instance jobs machines) : I.lp.IsCoveringPacking where
  coeff_nonneg := fun v q ↦ by
    rcases v with j | i
    · change 0 ≤ (if j = q.1.2 then I.load q.1.1 j else 0)
      split
      · exact I.load_nonneg _ _
      · norm_num
    · change 0 ≤ (if i = q.1.1 then 1 else 0)
      split <;> norm_num
  rhs_nonneg := by
    intro q
    change 0 ≤ (1 : ℝ)
    norm_num
  cost_nonneg := by
    intro v
    change 0 ≤ (1 : ℝ)
    norm_num

/--
The prefix LP used at an intermediate arrival. Its constraints are precisely
the eligible pairs whose job index is below `k`; retaining the future `z`
coordinates is harmless because the algorithm keeps them at zero.
-/
def lpThrough (I : Instance jobs machines) (k : ℕ) :
    FinitePrimalDual (PrimalVar jobs machines) (I.EligiblePairThrough k) where
  coeff v q :=
    match v with
    | Sum.inl j => if j = q.1.1.2 then I.load q.1.1.1 j else 0
    | Sum.inr i => if i = q.1.1.1 then 1 else 0
  rhs _ := 1
  cost _ := 1

/-- Every prefix LP inherits the covering/packing nonnegativity data. -/
theorem lpThrough_isCoveringPacking (I : Instance jobs machines) (k : ℕ) :
    (I.lpThrough k).IsCoveringPacking where
  coeff_nonneg := fun v q ↦ by
    rcases v with j | i
    · change 0 ≤ (if j = q.1.1.2 then I.load q.1.1.1 j else 0)
      split
      · exact I.load_nonneg _ _
      · norm_num
    · change 0 ≤ (if i = q.1.1.1 then 1 else 0)
      split <;> norm_num
  rhs_nonneg := by
    intro q
    change 0 ≤ (1 : ℝ)
    norm_num
  cost_nonneg := by
    intro v
    change 0 ≤ (1 : ℝ)
    norm_num

/--
The complete mutable state of the load-balancing algorithm. `weight` is `x`,
`slack` is `z`, and `dual` is the sparse 0/1 vector `y` produced by assigning
a job. `failedAt` stores the first job at which a phase fails.
-/
structure State (jobs machines : ℕ) where
  weight : Fin machines → ℝ
  assignment : Fin jobs → Option (Fin machines)
  slack : Fin jobs → ℝ
  dual : Fin jobs → Fin machines → ℝ
  failedAt : Option (Fin jobs)

/-- The tutorial initialization `x(j) = 1 / (2m)`, with all other variables zero. -/
def initialState (_I : Instance jobs machines) : State jobs machines where
  weight _ := 1 / (2 * (machines : ℝ))
  assignment _ := none
  slack _ := 0
  dual _ _ := 0
  failedAt := none

/-- The first explicit failure condition: the arriving job has no eligible machine. -/
def noEligibleMachine (I : Instance jobs machines) (i : Fin jobs) : Prop :=
  I.eligible i = ∅

/-- The second explicit failure condition: some current machine weight exceeds one. -/
def hasOverweightMachine (_I : Instance jobs machines) (s : State jobs machines) : Prop :=
  ∃ j, 1 < s.weight j

/-- Exactly the disjunction tested in Step (1) of the source algorithm. -/
def failureCondition (I : Instance jobs machines) (s : State jobs machines)
    (i : Fin jobs) : Prop :=
  I.noEligibleMachine i ∨ I.hasOverweightMachine s

/--
The eligible machine minimizing `load(i,j) * x(j)`. Machines are sorted by
their natural `Fin` order before `argmin`, so ties are broken deterministically.
-/
def chooseMachine (I : Instance jobs machines) (s : State jobs machines)
    (i : Fin jobs) : Option (Fin machines) :=
  ((I.eligible i).sort (· ≤ ·)).argmin fun j ↦ I.load i j * s.weight j

/-- The source predicate characterizing a valid choice, independent of tie-breaking. -/
def IsMinimumChoice (I : Instance jobs machines) (s : State jobs machines)
    (i : Fin jobs) (j : Fin machines) : Prop :=
  j ∈ I.eligible i ∧
    ∀ k ∈ I.eligible i, I.load i j * s.weight j ≤ I.load i k * s.weight k

theorem chooseMachine_spec (I : Instance jobs machines)
    {s : State jobs machines} {i : Fin jobs} {j : Fin machines}
    (h : I.chooseMachine s i = some j) : I.IsMinimumChoice s i j := by
  have hjarg : j ∈ ((I.eligible i).sort (· ≤ ·)).argmin
      (fun k ↦ I.load i k * s.weight k) := h
  constructor
  · have hjlist := List.argmin_mem hjarg
    exact ((I.eligible i).mem_sort (· ≤ ·)).1 hjlist
  · intro k hk
    apply List.le_of_mem_argmin (m := j)
    · exact ((I.eligible i).mem_sort (· ≤ ·)).2 hk
    · exact hjarg

/--
One deterministic transition of the normalized algorithm. A prior failure is
absorbing. Otherwise Step (1) is checked, then the selected machine `ell`
receives the job and the source updates are applied:

`z(i) = 1 - load(i,ell) * x(ell)`, `y(i,ell) = 1`, and
`x(ell) := x(ell) * (1 + load(i,ell) / 2)`.
-/
def step (I : Instance jobs machines) (s : State jobs machines)
    (i : Fin jobs) : State jobs machines := by
  classical
  exact
    match s.failedAt with
    | some _ => s
    | none =>
        if I.failureCondition s i then
          { s with failedAt := some i }
        else
          match I.chooseMachine s i with
          | none => { s with failedAt := some i }
          | some ell =>
              let p := I.load i ell
              let oldWeight := s.weight ell
              { weight := Function.update s.weight ell (oldWeight * (1 + p / 2))
                assignment := Function.update s.assignment i (some ell)
                slack := Function.update s.slack i (1 - p * oldWeight)
                dual := Function.update s.dual i (Function.update (s.dual i) ell 1)
                failedAt := none }

/--
The load-balancing transition as a reusable causal online process. The decision is
the assigned machine when the arrival succeeds and `none` when the phase has
failed; the detailed first-failure witness remains in the state.
-/
def process (I : Instance jobs machines) :
    Online.Process (Fin jobs) (State jobs machines) (Option (Fin machines)) where
  initial := I.initialState
  step s i :=
    let next := I.step s i
    (next, next.assignment i)

/-- The arrival list `0, ..., jobs - 1`. -/
def arrivals (_I : Instance jobs machines) : List (Fin jobs) :=
  List.ofFn id

/-- State after processing the first `k` arrivals (or after the first earlier failure). -/
def runPrefix (I : Instance jobs machines) (k : ℕ) : State jobs machines :=
  I.process.stateAfter (I.arrivals.take k)

/-- Final state after the finite arrival sequence. -/
def finalState (I : Instance jobs machines) : State jobs machines :=
  I.runPrefix jobs

/-- The algorithm's phase did not encounter either failure condition. -/
def Succeeded (I : Instance jobs machines) : Prop :=
  I.finalState.failedAt = none

/-- Every arriving job received an irrevocable machine assignment. -/
def AssignsAll (I : Instance jobs machines) : Prop :=
  ∀ i, ∃ j, I.finalState.assignment i = some j

/-- Total normalized load recorded by a state on machine `j`. -/
def stateAssignedLoad (I : Instance jobs machines) (s : State jobs machines)
    (j : Fin machines) : ℝ :=
  ∑ i, if s.assignment i = some j then I.load i j else 0

/-- Normalized load assigned to machine `j` after the first `k` arrivals. -/
def assignedLoadThrough (I : Instance jobs machines) (k : ℕ) (j : Fin machines) : ℝ :=
  I.stateAssignedLoad (I.runPrefix k) j

/-- Total normalized load assigned by the final phase state to machine `j`. -/
def assignedLoad (I : Instance jobs machines) (j : Fin machines) : ℝ :=
  I.stateAssignedLoad I.finalState j

/-- Turn a state `(x,z)` into the primal vector of `I.lp`. -/
def primalVector (_I : Instance jobs machines) (s : State jobs machines) :
    PrimalVar jobs machines → ℝ
  | Sum.inl j => s.weight j
  | Sum.inr i => s.slack i

/-- Turn the algorithm's rectangular `y` array into the dual vector on eligible pairs. -/
def algorithmDualVector (I : Instance jobs machines) (s : State jobs machines) :
    I.EligiblePair → ℝ :=
  fun q ↦ s.dual q.1.1 q.1.2

/-- Restrict a full dual vector to the constraints present in prefix `k`. -/
def restrictDual (I : Instance jobs machines) (y : I.EligiblePair → ℝ) (k : ℕ) :
    I.EligiblePairThrough k → ℝ :=
  fun q ↦ y q.1

/-- The total dual mass placed on eligible machines for one job. -/
def jobDualMass (I : Instance jobs machines) (y : I.EligiblePair → ℝ)
    (i : Fin jobs) : ℝ :=
  ∑ q, if q.1.1 = i then y q else 0

/--
The premise “a feasible dual solution assigning all jobs” used by the
load-balancing guarantee.
The first conjunct uses the shared finite-LP interface; the second says every
job constraint is tight at value one, equivalently giving dual objective
`jobs` in this unit-right-hand-side LP.
-/
def DualAssignsAll (I : Instance jobs machines) (y : I.EligiblePair → ℝ) : Prop :=
  I.lp.DualFeasible y ∧ ∀ i, I.jobDualMass y i = 1

/-- Primal feasibility for the shared finite covering LP of the first `k` arrivals. -/
def PrimalFeasibleThrough (I : Instance jobs machines) (k : ℕ)
    (s : State jobs machines) : Prop :=
  (I.lpThrough k).PrimalFeasible (I.primalVector s)

/--
The shared finite-LP primal objective for prefix `k`. Along `runPrefix k`, all
future slack coordinates remain zero, so this is exactly the source objective
containing the machine weights and the first `k` job slacks.
-/
def primalObjectiveThrough (I : Instance jobs machines) (k : ℕ)
    (s : State jobs machines) : ℝ :=
  (I.lpThrough k).primalObjective (I.primalVector s)

/-- Exact logarithmic bound proved in the source, replacing its asymptotic notation. -/
def logarithmicLoadBound (_I : Instance jobs machines) : ℝ :=
  Real.log (3 * (machines : ℝ)) / Real.log ((3 : ℝ) / 2)

end Instance
end
end UnrelatedMachines
end PrimalDual
Source
Niv Buchbinder and Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal--Dual Approach, https://www.tau.ac.il/~nivb/download/pd-survey.pdf, Chapter 8, pp. 193--196; normalized loads and eligibility on p. 194, Figure 8.1 on p. 194, and the load-balancing algorithm on p. 195.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me