Next: Strengthening Up: Pseudo-Boolean and Cardinality Constraints Previous: Inference and Resolution

## Learning and Relevance Bounds

The idea of relevance also has a natural generalization to the pseudo-Boolean setting. Recall the basic definition from Section 2.2:

Definition 3.15   Let be a clause and a partial assignment. Then is -irrelevant if the number of literals in that are either unvalued or true under is at least .

Proposition 3.16   Given a partial assignment and a Boolean clause , is -irrelevant if and only if .

Proof. In the Boolean case, the number of literals in that are either unvalued or true is since the right hand side of the constraint is always 1. So the irrelevance condition is

and the result follows.

In the pseudo-Boolean case, additional learning techniques are also possible. Before we present these ideas in detail, however, let us point out that some sort of inferential extension is needed if we are to overcome the shortcomings of DPLL as revealed by the pigeonhole and other problems. After all, recall Proposition 3.14: pseudo-Boolean inference generalizes Boolean resolution. So if we begin with a Boolean axiomatization (as we did in the pigeonhole problem), any derivation using our techniques will be reproducible using conventional resolution-based methods, and will therefore be of exponential length. (A majority of the inference steps in the various proofs of Proposition 3.2 are not resolution steps in that no literal cancellations occur.)

Subsections

Next: Strengthening Up: Pseudo-Boolean and Cardinality Constraints Previous: Inference and Resolution
Matt Ginsberg 2004-02-19