1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks -- the part I was stuck on was how to set up those inequalities for relating $x_{i,j}$ and $y_{i,j}$. The first three make sense to me since they imply an element is covered if either itself, or one of its two vertical neighbors is marked. But I'm not sure what that last inequality is doing: $y_{i,j} \le x_{i-1,j} + x_{i,j} + x_{i+1,j}$. Doesn't that contradict the first three inequalities? $\endgroup$ – tomocafe Jul 29 '17 at 16:48
  • 1
    $\begingroup$ @EvanW, I don't think it contradicts the first three inequalities (you can try it!). It ensures that a cell is only covered if it is marked, or the cell above/below it is marked. $\endgroup$ – D.W. Jul 29 '17 at 18:18
  • $\begingroup$ Ah, I understand now. Thank you for the clarification! $\endgroup$ – tomocafe Jul 29 '17 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.