Pseudo-Boolean and Cardinality Constraints
Roussel Olivier, Manquinho Vasco · Frontiers in artificial intelligence and applications · 2009
Pseudo-Boolean and cardinality constraints are a natural generalization of clauses. While a clause expresses that at least one literal must be true, a cardinality constraint expresses that at least n literals must be true and a pseudo-Boolean constraint states that a weighted sum of literals must be greater than a constant. These contraints have a high expressive power, have been intensively studied in 0/1 programming and are close enough to the satisfiability problem to benefit from the recents advances in this field. Besides, optimization problems are naturally expressed in the pseudo-Boolean context.