Binary optimization problem

Question

I am facing the following problem:

Let P be a fixed m x n finite matrix and D be a matrix of ones and zeros with the same dimensionality as P plus the following constraints:

• sum of row entries <= c1 (for each row)
• sum of column entries <= c2 (for each column)

• maximally c3 rows may contain ones

  ( c1, c2 and c3 are some fixed natural numbers)

The task is to find such D matrix (under those constraints), so that the sum of entries of (P.*D) is maximized.

Note that by ".*" I mean entry-by-entry product.

If you have any study material recommendations or a way to approach it, I will be happy for any suggestions. Thank you.

Answer 1

For the sake of simplicity, let $c_3 = m$. We then have the following binary program

$$\begin{array}{ll} \text{maximize} & \operatorname{tr} (P^T D)\\ \text{subject to} & D 1_n \leq c_1 \, 1_n\\ & D^T 1_m \leq c_2 \, 1_m\\ & D \in \{0,1\}^{m \times n}\end{array}$$

Relaxing the binary constraint, we have the following linear program

$$\begin{array}{ll} \text{maximize} & \operatorname{tr} (P^T D)\\ \text{subject to} & D 1_n \leq c_1 \, 1_n\\ & D^T 1_m \leq c_2 \, 1_m\\ & D \in [0,1]^{m \times n}\end{array}$$

Suppose that the optimal solution of the LP is $D^*$. We then use a rounding scheme

$$\rho_{\gamma} (x) := \begin{cases} 1 & \text{if } x \geq \gamma\\ 0 & \text{if } x < \gamma\end{cases}$$

in order to obtain a matrix $\rho_{\gamma} (D^*) \in \{0,1\}^{m \times n}$. We then adjust the threshold $\gamma \in [0,1]$ in an attempt to satisfy the constraint that at most $c_3$ rows contain ones, while still satisfying the two inequality constraints on the sum of the entries on each row and column.

Answer 2

This can be done in one shot if you have an integer linear programming engine. Let's define a vector variable $q\in\{0,1\}^m$. We'll set this up so that all of the elements of row $i$ of $D$ must be zero if $q_i=0$. Then we have \begin{array}{lll} \text{maximize} & \sum_{ij} P_{ij} D_{ij} \\ \text{subject to} & D_{ij} \leq q_i & i=1,2,\dots, m, ~j=1,2,\dots n \\ & \sum_j D_{ij} \leq c_1 & i=1,2,\dots, m \\ & \sum_i D_{ij} \leq c_2 & j=1,2,\dots, n \\ & \sum_i q_i \leq c_3 \\ & D\in\{0,1\}^{m\times n} \\ & q\in\{0,1\}^m \end{array}