Methods and Tools for Pseudo-Boolean Problems

Pseudo-Boolean problems are a generalization of Boolean problems and combine Boolean algebra with arithmetic. A pseudo-Boolean problem is defined by equations and inequalities between integer polynomials in 0-1 variables. We describe methods and tools for solving pseudo-Boolean problems that combine techniques from automated deduction and operations research. The basic idea is to compute strong valid inequalities for the underlying set of 0-1 vectors