Solution (source code)

= Solution

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
$$
\begin{gathered}
\min y,\\
\sum_iw_iz_i\leq y,\qquad\sum_iw_i(1-z_i)\leq y,\\
z_i\in\{0,1\},\qquad y\geq0.
\end{gathered}
$$
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:
$$
\boxed{\min\sum_iw_iz_i\quad\text{subject to}\quad 2\sum_iw_iz_i\geq s,\quad z_i\in\{0,1\}.}
$$
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.