ABSTRACT
The Boolean Optimization Problem (BOOP) represents a large class of binary optimization models, including weighted versions of Set Covering, Graph Stability, Set Partitioning, and Maximum Satisfiability problems. These problems are all NP-hard, and exact (provably convergent) optimization methods encounter severe performance difficulties in these particular applications, being dominated by heuristic search methods even for moderately sized problem instances.
