Finding the optimal binary matrix Let $a$ be an $n \times 1$ positive vector, $b$ be an $m \times 1$ positive vector, and $X$ be an $m \times n$ matrix where $x_{ij} \in \{0,1\}$. I want to find the $X$ that minimizes $\sum_{i=1}^m v_i$, where $v = b-Xa$, subject to


*

*summation of each column in $X$ should be either $0$ or $1$

*$v_i \geq 0$
 A: Notice that since you are summing the end results, $B$ has no bearing on the choice of $X$, and that leaves you minimizing
$$
\sum_{i=1}^n \sum_{j=1}^m a_i x_{ji}
 = \sum_{i=1}^n a_i \left( \sum_{j=1}^m x_{ji} \right),
$$
so you should set to 1 all $x_{ji}$ in the rows, where $a_j<0$ and otherwise, set the rest of $x_{ji}=0$.
A: Let $\rm v := X a - b$, where $\rm a, b$ are given positive vectors. Hence,
$$1_m^{\top} \mathrm v = 1_m^{\top} \mathrm X \, \mathrm a - 1_m^{\top} \mathrm b = \mbox{tr} (\mathrm a 1_m^{\top} \mathrm X) - 1_m^{\top} \mathrm b = \langle 1_m \mathrm a^{\top}, \mathrm X \rangle - 1_m^{\top} \mathrm b$$
Thus, we have the following binary integer program (IP) in $\mathrm X \in \{0,1\}^{m \times n}$
$$\begin{array}{ll} \text{minimize} & \langle 1_m \mathrm a^{\top}, \mathrm X \rangle\\ \text{subject to} & 0_n^{\top} \leq 1_m^{\top} \mathrm X \leq 1_n^{\top}\\ & \mathrm X \mathrm a \geq \mathrm b\\ & \mathrm X \in \{0,1\}^{m \times n}\end{array}$$
Vectorizing, we obtain
$$\begin{array}{ll} \text{minimize} & (\mathrm a \otimes 1_m)^{\top} \mbox{vec} (\mathrm X) \rangle\\ \text{subject to} & 0_n \leq (\mathrm I_n \otimes 1_m^{\top}) \,\mbox{vec} (\mathrm X) \leq 1_n\\ & (\mathrm a^{\top} \otimes \mathrm I_m) \, \mbox{vec} (\mathrm X) \geq \mathrm b\\ & \mbox{vec} (\mathrm X) \in \{0,1\}^{m n}\end{array}$$
