I have a list positive integer. My goal is to partition all the integers into two subsets such that the sum of the subsets are as close as possible. There are no constraints.
I immediately thought of this as a partition problem, and approximation algorithms, but I am supposed to solve this using linear programming.
Can I solve this using linear programming, if yes, can you give me a hint?
$x_{ij}=1$ if and only if integer $n_i$ is put in set $j\in \{1,2\}$.
You want to minimize $$ \left| \sum_{i}n_{i}x_{i1} - \sum_{i}n_{i}x_{i2} \right| $$ subject to $$ x_{i1} + x_{i2} = 1\quad \forall n_i $$ (each integer is in set $1$ or $2$, exclusively)