Resolution vs. cutting plane solution of inference problems: Some computational experience (Q1100093)

Resolvents in the propositional calculus correspond to certain cutting planes in integer programming models of inference problems. We compare the performance of a rudimentary cutting plane algorithm that uses only resolvents as cuts with that of `set-of-support' resolution on random inference problems. The cutting plane algorithm is orders of magnitude faster on problems in which the premises do not imply the given proposition (i.e., the majority of random problems), and moderately faster on other random problems.