Optimal covering of 2D matrix elements given spatial constraints

Question

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction.

I've generalized and reduced the problem to this:

Given an $M \times N$ matrix with elements in $\{0, 1\}$, cover all the $1$ elements according to the following rules:

• "Marking" an element covers that element as well as the elements directly above and below
• A maximum of $\frac{N}{2}$ elements can be marked in any row of the matrix

while minimizing the number of $1$ elements that are covered by an adjacent element but not marked itself.

For example,

Let $M = N = 4$ and consider the following matrix:

$$ \begin{bmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} $$

Because $N = 4$, only 2 or less elements may be marked per row.

An optimal solution is as follows, where marked elements are shown in red, and elements that are covered but not marked are shown in blue.

$$ \begin{bmatrix} \color{red}{1} & 0 & \color{blue}{1} & \color{red}{1}\\ 0 & \color{red}{1} & \color{red}{1} & 0\\ \color{red}{1} & \color{red}{1} & \color{blue}{1} & \color{blue}{1}\\ 0 & 0 & 0 & \color{red}{1} \end{bmatrix} $$

In this solution, there are three $1$ elements that are covered but not marked (in blue).

For this problem, I need an actual assignment of the marks for each row, not just the final minimum cost.

---

The spatial relationship between neighboring elements initially led me to think about the problem in terms of a graph, so I tried setting it up as a minimum-cost maximum-flow problem, but I couldn't figure out how to model the flow graph.

Then I started looking into set-covering and ILP, but I'm not sure how to specify the rule about the relationship between vertical neighbors as a constraint.

Answer 1

Yes, this can be expressed as an instance of integer linear programming and then solved with an ILP solver. I don't know if there's a better way (for instance, I don't know if the problem is NP-complete).

We'll define zero-or-one variables $x_{i,j}$ and $y_{i,j}$, with the intention that $x_{i,j}=1$ means that cell $(i,j)$ of the matrix is marked and $y_{i,j}=1$ means that cell $(i,j)$ is covered. Let $A$ denote the matrix. Then we have constraints to ensure that all 1's in the matrix are covered: $y_{i,j} \ge 1$ for all $i,j$ such that $A_{i,j} = 1$. Also, we have constraints to ensure that the $x$'s and $y$'s are related appropriately:

$$y_{i,j} \ge x_{i,j} \qquad y_{i,j} \ge x_{i-1,j} \qquad y_{i,j} \ge x_{i+1,j}$$

$$y_{i,j} \le x_{i-1,j} + x_{i,j} + x_{i+1,j}$$

To impose the requirement that at most $N/2$ cells are marked in each row, add the constraints

$$\sum_j x_{i,j} \le N/2.$$

Finally, notice that $y_{i,j}-x_{i,j}$ is $1$ if cell $(i,j)$ is covered but not marked, and $0$ otherwise. Therefore, the objective function is:

$$\sum_{i,j} y_{i,j}-x_{i,j}$$

Now feed this to an ILP solver, and let it do what it can to try to solve it.