Return to Revisions

You can approximate the problem by minimizing the range via integer linear programming. Let binary decision variable $x_{i,j}$ indicate whether number $i\in N$ is assigned to group $j\in\{1,\dots,n\}$. The problem is to minimize $u-\ell$ subject to: \begin{align} \sum_j x_{i,j} &=1 &&\text{for all $i$}\\ \sum_i x_{i,j} &= m &&\text{for all $j$}\\ \ell \le \sum_i a_i x_{i,j} &\le u &&\text{for all $j$} \end{align} To obtain a formulation for the min-max or max-min problem, omit the parts involving $\ell$ or $u$, respectively.