Skip to content

6.6 Min-max, max-min and the range

Technique: continuous with continuous · Script: python/cap03_links.py · All the techniques

Three fairness objectives, often confused: min-max (minimise the largest load), max-min (maximise the smallest load) and range (minimise the gap between the largest and the smallest).

The constraints

With \(\ell_k\) the load of resource \(k \in \{1, 2, \dots, m\}\):

\[ \begin{aligned} \text{min-max:}&\quad \min z \quad\text{with}\quad z \ge \ell_k,\ \forall k &&(m \text{ constraints}),\\ \text{max-min:}&\quad \max u \quad\text{with}\quad u \le \ell_k,\ \forall k &&(m \text{ constraints}),\\ \text{range:}&\quad \min\,(z - u) \quad\text{with both} &&(2m \text{ constraints}). \end{aligned} \]

The proof

Each is the maximum auxiliary variable (or minimum) with the exchange argument in the right direction: in a \(\min z\) the variable \(z\) falls to the maximum of the loads; in a \(\max u\) it rises to the minimum. In the range both pressures are present and the two conclusions hold together.

The three objectives are not comparable

On the five-weight instance \(p = (3, 5, 2, 4, 7)\) to be split between two workers (total \(21\)), the three versions choose the same split \((11, 10)\) — the best possible, because the total is odd — but their optimal values are \(11\), \(10\) and \(1\). They are three different numbers describing the same solution. Comparing "\(z = 11\)" of a min-max with "\(z = 1\)" of a range means nothing. And the optimal solutions need not coincide either: with more than two resources, min-max and max-min in general choose different splits.

The strength of the relaxation

The min-max on that instance gives \(z(\mathit{LP}^+) = 21/2 = 10.5\) against \(z(\mathit{MILP}) = 11\): the relaxation splits the weights exactly in half, which integrality does not allow.

In gurobipy

T = m.addVar(name="T")
m.addConstrs((T >= load[k] for k in range(K)), name="max")
m.setObjective(T, GRB.MINIMIZE)