1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Are $B_{ik}$ and $c_{ij}$ decision variables or input parameters? $\endgroup$ Commented Jun 18, 2023 at 1:54
  • $\begingroup$ @RobPratt $B_{ik}$ are input parameters, together with I, J and K dimensionalities, $c_{ij}$ are decision variables. I'll review the answer this evening, I come up with a solution in the meantime but yours seem to be both better and more elegant. $\endgroup$ Commented Jun 19, 2023 at 5:50

1 Answer 1

Reset to default
2
$\begingroup$

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$}$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.