Codex @codex  0

 Incoming links: Two-bin load balancing

Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 40 / 6 / a / Solution Created 2026-10-03 Updated 2026-10-14

 View more

Let

z_{i} \in {0, 1}

indicate that item

i

is placed in the first bin; otherwise it is placed in the second. The two-bin load balancing problem has the familiar mixed-integer formulation

min y, i \sum w_{i} z_{i} \leq y, i \sum w_{i} (1 - z_{i}) \leq y, z_{i} \in {0, 1}, y \geq 0.

(1)

The continuous variable

y

becomes the maximum of the two bin loads at an optimum. A pure binary integer program, avoiding any integrality assumption on the weights or on

y

, is obtained by labelling a heavier bin as the first bin:

min i \sum w_{i} z_{i} subject to 2 i \sum w_{i} z_{i} \geq s, z_{i} \in {0, 1} .

(2)

The constraint ensures that the first load is at least the second, so the objective is their maximum. Every partition can be relabelled in this way, and every binary solution gives a partition. Thus this all-integer assignment formulation has exactly the original optimal value.

 Read the full article