CNF form of the logical $atleast(b) x_{i,k}$

Question

Suppose there exists the following logical expression:

$$(\sum_{i=1}^I x_{(i,k)} \leq b) \implies (z_{(j,k)}=1) \quad \forall j \in J, k \in K \tag{1}$$

where all of variables, $x_{(i,k)}$ and $z_{(j,k)}$, are binary. I know this logical form can easily be translated into its linear form by $BigM$ formulation. However, as all of the variables are binary, I guess, there should be a purely logical form translation based on $CNF/DNF$ to convert that. What I have tried is:

$$(\text{atmost(b)}_i x_{(i,k)}) \implies (z_{(j,k)}=1) \quad \forall j \in J, k \in K \quad => $$ $$(\lnot \text{atmost(b)}_i x_{(i,k)}) \lor(z_{(j,k)}) \quad \forall j \in J, k \in K \quad => $$ $$(\text{atleast(b+1)}_i x_{(i,k)}) \lor(z_{(j,k)}) \quad \forall j \in J, k \in K \quad => $$ $$\bigwedge (\bigvee x_{(i,k)}) \lor(z_{(j,k)}) \quad \forall j \in J, k \in K \quad => $$

At the moment, I am not sure how can I transform the first clause of the last expression and am wondering if, someone can advise me.

P.S: The atleast expression can be written as the following form:

$$ atleast(k)_{i} x_{i} \iff \bigwedge_{S \subset I | | S|=n-k+1} (\bigvee_{i \in S} x_{i}) $$

And the first $\bigwedge_{S}$ is where I am getting stuck to explode the related sets.

Answer 1

For simplicity, omit the $j$ and $k$ indices. You want to enforce $$\sum_i x_i \le b \implies z=1.\tag1\label1$$ As you mentioned, a natural approach is the big-M formulation $$b+1-\sum_i x_i \le Mz,$$ and you can take $M=b+1$, yielding $$\sum_i x_i + (b+1)z \ge b+1 \tag2\label2.$$ For CNF, you can instead first rewrite \eqref{1} as $$\left(\sum_i x_i \ge b+1\right) \lor z.$$ Now think of all the $(b+1)$-subsets $S$ of $\{1,\dots,I\}$ and rewrite as $$\left(\bigvee_{S:|S|=b+1} \bigwedge_{i\in S} x_i\right) \lor z,$$ equivalently, $$\left(\bigwedge_{T:|T|=I-b} \bigvee_{i\in T} x_i\right) \lor z,$$ equivalently, $$\bigwedge_{T:|T|=I-b} \left(\bigvee_{i\in T} x_i \lor z\right),$$ which yields linear constraints $$\sum_{i\in T} x_i + z \ge 1 \quad \text{for all $T$ such that $|T|=I-b$}.\tag3\label3$$ Notice that aggregating \eqref{3} yields $$ \sum_{T:|T|=I-b} \left(\sum_{i\in T} x_i + z\right) \ge \sum_{T:|T|=I-b} 1 \\ \sum_{T:|T|=I-b} \sum_{i\in T} x_i + \binom{I}{I-b}z \ge \binom{I}{I-b} \\ \binom{I-1}{I-b-1} \sum_{i=1}^I x_i + \binom{I}{I-b}z \ge \binom{I}{I-b} \\ \binom{I-1}{b} \sum_{i=1}^I x_i + \binom{I}{b}z \ge \binom{I}{b} \\ \sum_{i=1}^I x_i + \frac{I}{I-b}z \ge \frac{I}{I-b}, $$ but this aggregation is generally weaker than \eqref{2}.

Answer 2

Since the $\bigwedge$ and $\bigvee$ don't have anything to do with the $j$ and $k$, you can use Distribution to go from:

$$\bigwedge (\bigvee x_{(i,k)}) \lor(z_{(j,k)}) \quad \forall j \in J, k \in K \quad $$

to:

$$\bigwedge \left((\bigvee x_{(i,k)}) \lor(z_{(j,k)})\right) \quad \forall j \in J, k \in K \quad $$

Also: So far I have just paid attention to your last expression… but now that I am looking at the one before it: I think you should swap the $\bigwedge$ and $\bigvee$, to capture all possible ways (thus $\bigvee$) to get at least $b+1$ terms $x_{(i,k)}$ (thus $\bigwedge$). Of course, with that, my Distribution above is unnecessary and in fact the resulting formula is in DNF already