Modularity constraints and pseudo-Boolean encodings

To encode a modularity constraint in this way, we first note that we can easily capture an equality axiom of the form

$$\sum_i w_i l_i = k$$ (34)

in a pseudo-Boolean setting, simply by rewriting (34) as the pair of constraints

$$\begin{eqnarray*} \sum_i w_i l_i & \geq & k \\ \sum_i w_i \overline l_i & \geq & \sum_i w_i - k \end{eqnarray*}$$

In what follows, we will therefore feel free to write axioms of the form (34).

We now denote by $\lfloor x \rfloor$ the floor of $x$, which is to say the smallest integer not greater than $x$, and have:

Proposition 3.19   Suppose that we have a modularity constraint of the form (33). We set $w=\sum_i w_i$ and introduce new variables $s_i$ for $i=1,\dots,\lfloor \frac wm \rfloor$. Then (33) is equivalent to

$$\sum_i w_i l_i + \sum_i ms_i = m\Bigl\lfloor \frac wm \Bigr\rfloor + n$$ (35)

Proof. Reducing both sides of (35) mod m shows that (35) clearly implies (33). For the converse, note if (33) is satisfied, there is some integer $s$ such that $\sum_i w_i l_i = sm + n$. Further, since $\sum_i w_il_i \leq \sum_i w_i = w$, it follows that $sm+n \leq w$, so that $s\leq \frac{w-n}m\leq \frac wm$ and thus $s\leq \lfloor \frac wm \rfloor$. We can therefore satisfy (35) by valuing exactly that many of the $s_i$ to be true.         $\mathchoice{\vcenter{\hrule height.4pt \hbox{\vrule width.4pt height3pt \kern ... ...vrule width.3pt height1.5pt \kern 1.5pt \vrule width.3pt} \hrule height.3pt}}$

Understand that the introduction of new variables here is not part of any intended inference procedure; it is simply the fashion in which the modularity constraints can be captured within a pseudo-Boolean setting.

In the case where all of the constraints are parity constraints, we have:

Proposition 3.20   A set of mod 2 constraints can be solved in polynomial time.

Proof. An individual constraint (recall that $\oplus$ corresponds to exclusive or, or addition mod 2)

$$l\oplus \oplus_i l_i = n$$

can be viewed simply as defining

$$l=n\oplus\oplus_i l_i$$

and this definition can be inserted to remove $l$ from the remaining constraints. Continuing in this way, we either define all of the variables (and can then return a solution) or derive $1=0$ and can return failure.         $\mathchoice{\vcenter{\hrule height.4pt \hbox{\vrule width.4pt height3pt \kern ... ...vrule width.3pt height1.5pt \kern 1.5pt \vrule width.3pt} \hrule height.3pt}}$

This result, which can be thought of as little more than an application of Gaussian elimination, is also an instance of a far more general result of Schaefer's Schaefer:complexity.

Proposition 3.21   A set of mod 2 constraints can be solved in polynomial time using the pseudo-Boolean axiomatization given by (35).

Proof. The technique is unchanged. When we combine

$$l+\sum_i l_i + 2\sum_i s_i = n$$

and

$$l+\sum_i l'_i + 2\sum_i s'_i = n'$$

we get

$$\sum_i l_i + \sum_i l'_i + 2(\sum_i s_i + \sum_i s'_i + l) = n+n'$$

and can now treat $l$ as one of the auxiliary $s$ variables. Eventually, we will get

$$2 \sum_i s_i = n$$

for a large (but polynomially sized) set $S$ of auxiliary variables and some $n$ that is either even or odd. If $n$ is even, we can value the variables and return a solution; if $n$ is odd and there are $k$ auxiliary variables, we have

$$\sum_i s_i = \frac n2$$

so

$$\sum_i s_i \geq \frac{n+1}2$$ (36)

since each $s_i$ is integral. But we also have

$$2 \sum_i \overline s_i \geq 2k-n$$

so that

$$\sum_i \overline s_i \geq k - \frac{n-1}2$$ (37)

Adding (36) and (37) produces $k\geq k+1$, a contradiction.         $\mathchoice{\vcenter{\hrule height.4pt \hbox{\vrule width.4pt height3pt \kern ... ...vrule width.3pt height1.5pt \kern 1.5pt \vrule width.3pt} \hrule height.3pt}}$

Let us point out, however, that if a mod 2 constraint is encoded in a normal Boolean way, so that $x\oplus y \oplus z=1$ becomes

$$x\vee y\vee z$$ (38)

$$x \vee \neg y \vee \neg z$$

$$\neg x \vee y \vee \neg z$$

$$\neg x \vee \neg y \vee z$$ (39)

it is not obvious how the pseudo-Boolean analog can be reconstructed. Here is the problem we mentioned at the beginning of this section: it is not enough to simply extend the representation; we need to extend the inference methods as well. In fact, even the question of whether families of mod 2 constraints can be solved in polynomial time by pseudo-Boolean methods without the introduction of auxiliary variables as in (35) is open. Other authors have also considered the problem of reasoning with these constraints directly [LiLi2000].