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.