Problem statement
Let $\beta \in \{0, 1\}$ for brevity. A set of $K$ numbers $M_k$, represented as individual bits $B_{ik} \in β $, must be distributed to a set of $ J \le K$ pairs $F_j = (c_{ij} \in β , m_{ij} \in β)$ — please excuse the probably wrong notation, it's a pair of numbers $c$ and $m$ decomposed as bits — such that:
- $M_k$ must be distributed to at least one $F_j$
- if $M_k$ is distributed to $F_j$, then $(m_{ij} = 1) \implies (B_{ik} = c_{ij})$
- $\textrm{min}_j \sum_i m_{ij}$ is maximum
"Degenerate" cases solutions
$J = 1$
$c = \mathrm{AND_k}\ M_k$
$m = c\ \mathrm{OR}\ (\mathrm{AND_k}\ \mathrm{NOT}(M_k))$
$\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{NOT}$ are bitwise.
$J = K$
$c_{ik} = B_{ik}$
$m_{ik} = 1$
A possible integer program
Auxiliary variables
$µ_{jk} \in β$: if $M_k$ is distributed to $F_j$.
$e_{ijk} \in β$: if $c_{ij}$ is constrained ($M_k$ is distributed to $F_j$ and $m_{ij} = 1$)
$s_{j} \in \mathbb{N}$: sum of $m_{ij}$
$s \in \mathbb{N}$: minimum sum of $s_{j}$
\begin{align*} \mathrm{max} &\quad s \\ s.t. & \\ \sum_j µ_{jk} &\ge 1 \\ µ_{jk} + m_{ij} &\le e_{ijk} + 1 \\ µ_{jk} &\ge e_{ijk} \\ m_{ij} &\ge e_{ijk} \\ c_{ij} &\le m_{ij} \\ B_{ik} - c_{ij} &\le \phantom{-(}1 - e_{ijk} \\ B_{ik} - c_{ij} &\ge -(1 - e_{ijk})\\ s_j &= \sum_i m_{ij} \\ s &\le s_j \\ \end{align*}
Missing part
This formulation should be enough to get a feasible and (almost) optimal solution. "Almost" because the actually optimal solution also minimize $\mathrm{max}_k \sum_j µ_{jk}$, i.e. $M_k$ ought to be handled by the minimum number of F.
It's easy to check afterwards if $F_j$ handles $M_k$ (the test is $M_k\ \mathrm{AND}\ m_j = c_j$), but I'd like to have the corresponding $µ_{jk}$ set directly in the program.
However I was not able to come up with a linear set of constraints that can express
\begin{align*} µ_{jk} = \mathrm{AND}_i\ ((m_{ij} = 1) \implies (B_{ik} = c_{ij})) \end{align*}
i.e. if ALL the bits of $c_j$ for which the corresponding bits of $m_j$ are set to 1 are equal to the corresponding bits of $M_k$, then the latter is distributed to $F_j$ — it's the other way around w.r.t the constraints above (with the current formulation one can have e.g. $µ_{2,1} = 0$ even if $F_2$ actually handles $M_1$ too, just because the solution happened to map $M_1$ to $F_1$) — but the problem is that the constraint should work only in $F_j \longrightarrow M_k$ direction, without forcing $µ_{jk} = 0$.
You want to enforce the logical proposition $$\mu_{jk} \iff \bigwedge_i (m_{ij} \implies (B_{ik} \iff c_{ij})) \tag1\label1$$
First rewrite part of the proposition in conjunctive normal form (CNF): $$ m_{ij} \implies (B_{ik} \iff c_{ij}) \\ m_{ij} \implies ((B_{ik} \implies c_{ij}) \land (c_{ij} \implies B_{ik})) \\ \lnot m_{ij} \lor ((\lnot B_{ik} \lor c_{ij}) \land (\lnot c_{ij} \lor B_{ik})) \\ (\lnot m_{ij} \lor \lnot B_{ik} \lor c_{ij}) \land (\lnot m_{ij} \lor \lnot c_{ij} \lor B_{ik}) $$
Now rewrite the forward direction of \eqref{1} in CNF: $$ \mu_{jk} \implies \bigwedge_i (m_{ij} \implies (B_{ik} \iff c_{ij})) \\ \lnot \mu_{jk} \lor \bigwedge_i \left((\lnot m_{ij} \lor \lnot B_{ik} \lor c_{ij}) \land (\lnot m_{ij} \lor \lnot c_{ij} \lor B_{ik}) \right) \\ \bigwedge_i \left((\lnot \mu_{jk} \lor \lnot m_{ij} \lor \lnot B_{ik} \lor c_{ij}) \land (\lnot \mu_{jk} \lor \lnot m_{ij} \lor \lnot c_{ij} \lor B_{ik}) \right), $$ yielding linear constraints \begin{align} (1-\mu_{jk}) + (1-m_{ij}) + (1-B_{ik}) + c_{ij} \ge 1 &&\text{for all $i,j,k$} \\ (1-\mu_{jk}) + (1-m_{ij}) + (1-c_{ij}) + B_{ik} \ge 1 &&\text{for all $i,j,k$} \end{align} Equivalently, \begin{align} \mu_{jk} + m_{ij} + B_{ik} - c_{ij} \le 2 &&\text{for all $i,j,k$} \\ \mu_{jk} + m_{ij} + c_{ij} - B_{ik} \le 2 &&\text{for all $i,j,k$} \end{align}
Now consider the backward direction of \eqref{1}: $$ \bigwedge_i (m_{ij} \implies (B_{ik} \iff c_{ij})) \implies \mu_{jk} $$ One approach is to rewrite as \begin{align} (m_{ij} \implies (B_{ik} \iff c_{ij})) &\implies f_{ijk} \tag2\label2 \\ \bigwedge_i f_{ijk} &\implies \mu_{jk} \tag3\label3 \end{align} Rewrite \eqref{2} in CNF: $$ \lnot (m_{ij} \implies (B_{ik} \iff c_{ij})) \lor f_{ijk} \\ \lnot \left((\lnot m_{ij} \lor \lnot B_{ik} \lor c_{ij}) \land (\lnot m_{ij} \lor \lnot c_{ij} \lor B_{ik})\right) \lor f_{ijk} \\ \left(\lnot (\lnot m_{ij} \lor \lnot B_{ik} \lor c_{ij}) \lor \lnot (\lnot m_{ij} \lor \lnot c_{ij} \lor B_{ik})\right) \lor f_{ijk} \\ \left((m_{ij} \land B_{ik} \land \lnot c_{ij}) \lor (m_{ij} \land c_{ij} \land \lnot B_{ik})\right) \lor f_{ijk} \\ (m_{ij} \lor f_{ijk}) \land (B_{ik} \lor c_{ij} \lor f_{ijk}) \land (\lnot B_{ik} \lor \lnot c_{ij} \lor f_{ijk}), $$ yielding linear constraints \begin{align} m_{ij} + f_{ijk} &\ge 1 &&\text{for all $i,j,k$} \\ B_{ik} + c_{ij} + f_{ijk} &\ge 1 &&\text{for all $i,j,k$} \\ (1-B_{ik}) + (1-c_{ij}) + f_{ijk} &\ge 1 &&\text{for all $i,j,k$} \end{align} Finally, rewrite \eqref{3} in CNF: $$ \lnot \bigwedge_i f_{ijk} \lor \mu_{jk} \\ \bigvee_i \lnot f_{ijk} \lor \mu_{jk}, $$ yielding linear constraints $$\sum_i (1-f_{ijk}) + \mu_{jk} \ge 1 \quad \text{for all $j,k$}$$