Skip to main content
added 46 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

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 S_j$$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.

You can approximate the problem by minimizing the range via integer linear programming. Let binary decision variable $x_{i,j}$ indicate whether $i\in S_j$. 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.

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.

Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

You can approximate the problem by minimizing the range via integer linear programming. Let binary decision variable $x_{i,j}$ indicate whether $i\in S_j$. 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.