The maximum monomial agreement (MMA) problem involves finding a single logical conjunction that best separates a weighted set of positive and negative examples, represented as binary vectors. This problem is relevant for boosting methods for classifiers. In this talk we will discuss Goldberg and Eckstein's branch-and-bound algorithm for MMA, and it's implementation in the PEBBL (Parallel Enumeration and Branch-and-Bound Library) general-purpose branch-and-bound framework. We will mention some of PEBBL's unique features. We will show computational results for some examples from the Hungarian heart dataset and spam datasets on a distributed memory parallel computer. One of the most challenging examples scales almost perfectly to 8000 processors.

Co-authors: Jonathan Eckstein (Rutgers University), William Hart (Sandia National Laboratories)