Binary matrix optimization problem with element co-dependence

Question

Suppose we have an optimization problem where we want to find a binary matrix $A \in \{0, 1\}^{n \times m}$ that minimizes the score function defined as $$S(A) = \sum^n_i \sum^m_j f_{ij}(a_{i-1j}, a_{ij}, a_{i+1j}, a_{ij-1}, a_{ij+1}) $$

where all $f_{ij}$ are known, real-valued and bound within $[-w, w]$, except for every $f_{ij}(1, 1, \cdot, \cdot, \cdot)$ and $f_{ij}(\cdot, 1, 1, \cdot, \cdot)$ which are $+\infty$. In other words, the individual score of any $a_{ij}$ depends on it and its orthogonal neighbors and no consecutive $1$s are allowed in any column. For the boundary elements, $f_{ij}$ depends only on the subset of its arguments that exist in $A$.

1. Is there any efficient algorithm to optimally solve it?
2. Is there any efficient algorithm to approximate it?

Any hints/references as to how I can approach solving/approximating this problem (if possible)?

Answer 1

If the functions $f_{i,j}$ can be arbitrary (subject to the constraints in your question), then the problem is $\mathsf{NP}$-hard and inapproximable in polynomial-time unless $\mathsf{P}=\mathsf{NP}$. Unfortunately, the proof is a bit technical. It is a reduction from rectilinear planar 3-SAT. Essentially you can embed a 3-SAT formula into a grid $A$ (to be filled) and use the functions $f_{i,j}$ to enforce some additional filling rules. In particular, if $A$ violates some rule we will have $S(A)>0$. If $A$ does not violate any rule we will have $S(A)=0$. All the rules can be obeyed if and only if the 3-SAT instance admits a solution.

To ease the description allow me to forget about the constraint of not having two consecutive $1$s on a column.

There are essentially four types of cells:

• Empty cells: their corresponding function equals $0$ if the value in the cell is $0$ and $1$ otherwise. No other function will depend on these cells. We can essentially set these cells to $0$ and forget about them.
• Variable cells: each of these cells is associated with a variable $x_i$ of the 3-SAT instance. Writing $0$ in the cell means setting $x_i$ to false, while writing $1$ means setting $x_i$ to true. You can imagine these cells as generating a true or false "signal". The function associated to these cells is the constant function $0$.
• Wire cells: these cells force you to copy the same value of some fixed neighboring cell, effectively carrying the signal from the variable cells to the clause cells (see the next item). Writing the "wrong" value in these cells will cause the associate function to equal $1$. Otherwise, the function will equal $0$.
• Clause cells: these cells represent a clause from the 3-SAT instance are always neighbors of $3$ wire cells, which carry the signal encoding the truth values of the variables in that clause. The function equals $0$ if these truth values satisfy the clause and $1$ otherwise. Notice that the function does not depend on the value written in the cell itself.

Here is an example showing a 3-SAT formula, it's planar rectilinear embedding, and the corresponding (still unfilled) grid with empty cells, variable cells, wire cells, and clause cells shown in white, blue, gray, and red, respectively. The arrow in the wire cells shows which value should be copied.

The matrix on the left in the next figure shows a solution $A$ with $S(A)=0$. To handle the restriction prohibiting two consecutive $1$s on the same column it suffices to (i) ensure that, in the embedding, no two wire cells referring to different variables appear as neighbors, (ii) flip the meaning of the values on the wire cells in a checkerboard pattern (see the matrix on the right).