I've got a CSP which is based on constraining bit vector variables. It is explained below through an example, followed by the full definition. So, what I'm concerned about is if you have some idea if this CSP ....
- can be formulated as a max-flow-min-cap network. It would be some 'combinatorial' fashioned network, though, or several networks together for one instance.
- can be solved with some dynamic programming involved.
I gave it many thoughts on how to exploit it through lattice/König theorems etc. Perhaps someone recognices to find something interesting. Of course, it can be solved in practice well by smt-solvers, but I'm trying to get a deeper understanding. So, you're welcome to check the example below and share your thoughts.
Example Let $$ A= \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ \end{bmatrix} $$.
The set of all bit numbers of length $l$ is represented by $B^l$. Consider the instance variables $r_i, c_j\in B^7$ for $\,\,i=1, \ldots, 5$, $\, j=1, \ldots, 4$ and examine the $2+3+5+4+6+6$ $A$-induced constraints \begin{alignat*}{21} c_1:=&\:\, r_1 \:\,& \land \:\,& r_2 \:\,& \land \:\,& r_3 \:\,& \land \:\,& r_4 \:\,& \:\,& \:\,& \land \:\,& r_6 \:\,& \:\,& \:\,& \not\subseteq \:\, & & & & & r_5,\:\:\,\: & & r_7 \\ c_2:=&\:\, r_1 \:\,& \:\,& \:\,& \:\,& \:\,& \land \:\,& r_4 \:\,& \land \:\,& r_5 \:\,& \:\,& \:\,& \land \:\,& r_7 \:\,& \not\subseteq \:\, & & r_2,\:\:\,\: & r_3,\:\:\,\: & & & r_6 \:\:\,\: & \\ c_3:=&\:\, r_1 \:\,& \:\,& \:\,& \land \:\,& r_3 \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \not\subseteq \:\, & & r_2,\:\:\,\: & & r_4,\:\:\,\: & r_5,\:\:\,\: & r_6,\:\:\,\: & r_7 \\ c_4:=&\:\, \:\,& \:\,& r_2 \:\,& \:\,& \:\,& \land \:\,& r_4 \:\,& \land \:\,& r_5 \:\,& \:\,& \:\,& \:\,& \:\,& \not\subseteq \:\, & r_1,\:\:\,\: & & r_3,\:\:\,\: & & & r_6,\:\:\,\: & r_7 \\ c_5:=&\:\, \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& r_6 \:\,& \:\,& \:\,& \not\subseteq \:\, & r_1,\:\:\,\: & r_2,\:\:\,\: & r_3,\:\:\,\: & r_4,\:\:\,\: & r_5 \:\:\,\: & & r_7 \\ c_6:=&\:\, \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& \:\,& r_7 \:\,& \not\subseteq \:\, & r_1,\:\:\,\: & r_2,\:\:\,\: & r_3,\:\:\,\: & r_4,\:\:\,\: & r_5,\:\:\,\: & r_6 \:\:\,\: & \end{alignat*}
Here, $\land$ is the and operator and $x\not\subseteq y$ means there is a bit position that is set in $x$, but not in $y$. To avoid confusion, in each of the six rows above the lhs is in $\not\subseteq$-relation to each of the listed variables on the rhs.
There are also restrictions on the search space. In general, there are two constraints per variable, each subject to a right and a left part of bit positions. In this example, we assume $r_1$ being restricted to concatenations $(B^3_1,B^4_2)\subsetneq B^7_3$. So, $(B^3_1,B^4_2)$ consists of all $3\times 6$ bit vectors that can be concatenated from elements from $B^3_1$ with elements from $B^4_2$. With these preparations, let's assume the complete setting of domains given by
\begin{align*} r_1 \in & \;(B^3_1,B^2_1\cup B^2_2),\\ r_2 \in & \;(B^3_1,B^2_1\cup B^2_2),\\ r_3 \in & \;(B^3_1,B^2_1\cup B^2_2),\\ r_4 \in & \;(B^3_1,B^2_1\cup B^2_2),\\ r_5 \in & \;(B^3_1,B^2_1),\\ r_6 \in & \;(\{001\},B^2_1),\\ r_7 \in & \;(\{001\},B^2_1) \end{align*} and \begin{align*} c_j \in & \;(B^3_1\cup \{000\},B^2_1\cup \{000\}), \text{ for } j=1, \ldots, 6 \end{align*}. So, now further restrictions apply on the $c_j$'s on their left three bit positions.
There is a feasible solution to this instance.
With that example, one may see what this CSP is about. To round it up, I state the complete definition.
Problem Definition Given a binary matrix $A=(a_{ij})$ consisting of $m$ distinct rows and $n$ distinct columns. We may call it an instance matrix. Let $r_1, \ldots, r_m$ and $c_1, \ldots, c_n$ be bit vector variables of fixed length $l\in \mathbb{N}$. We say that $r_i$ is incident with $c_j$ iff $a_{ij}$. Let $l_H, l_S \in \mathbb{N}$ be fixed, such that $l_H+l_S=l$. We denote the set of bit vectors of length $l^{\prime}$ by $B^{l^{\prime}}$, and its subset of those that have precisely $k$ bits set by $B^{l^{\prime}}_k$. Lets denote the bit vector of the first $l_S$ bit positions of $r_i$ by $r^S_i$, and the one of last $l_H$ bit positions by $r^H_i$. The same notation applies for the $c_j$'s. So, our variables are split into a concatenation $r_i=(r^H_i,r^S_i)$ and $c_j=(c^H_j,c^S_j)$ for $i=1, \ldots, m, \, j=1, \ldots n$. With that, we assign an individual split instance domain for every variable. Formally, let $$D^{(r)}=\left\{\left(d^{(r_i)}_H, d^{(r_i)}_S\right) \,\bigg\vert\,\, i=1, \ldots, m\right\}$$ and $$D^{(c)}=\left\{\left(d^{(c_j)}_H, d^{(c_j)}_S\right) \,\bigg\vert\,\, j=1, \ldots, n\right\}$$ be two families of given tuples of bit vector sets, where $d^{(r_i)}_H, d^{(c_j)}_H \subseteq B^{l_H}$ and $d^{(r_i)}_S, d^{(c_j)}_S \subseteq B^{l_S}$ for $i=1, \ldots, m, \, j=1, \ldots n$. Now, we have the total number of $0$'s in $A$- many constraints as follows.
$$c_j:=\bigwedge\limits_{r\in inc(c_j)}r \mkern-5mu \:\,\: \not\subseteq \:r \quad \forall r \notin inc(c_j)$$, where $inc(c_j)=\{r_i\, \vert \, a_{ij}\}$, and $c_j\in \left(d^{(c_j)}_H, d^{(c_j)}_S\right)$, $r_i\in \left(d^{(c_j)}_H, d^{(c_j)}_S\right)$ for $i=1, \ldots, m, \, j=1, \ldots n$.