Unrelated-Machines Load-Balancing Model and Algorithm
Definitionpd_unrelated_machinesThis module formalizes the normalized online load-balancing problem on unrelated machines and the Buchbinder–Naor primal–dual algorithm for it.
A normalized instance has machines, jobs arriving in this order, and a nonnegative normalized load for every job–machine pair; machine is eligible for job exactly when . The associated covering primal minimizes subject to
and its packing dual maximizes subject to for every job and for every machine . Prefix versions of the program keep only the constraints of the first jobs.
The algorithm is given as an executable causal online process. It initializes every machine weight to ; on arrival of job it declares failure if has no eligible machine or if some current weight exceeds ; otherwise it assigns irrevocably to an eligible machine minimizing (ties broken by machine order), sets and , and updates . 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 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 -updates live in a rectangular array inside the state.
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