Finding the optimal binary matrix

Question

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$

Answer 1

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}$$

Answer 2

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