The NP-hard Maximum Monomial Agreement (MMA) problem consists of finding a single logical conjunction that best fits a weighted dataset of “positive” and “negative” binary vectors. Computing classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we describe an exact branch and bound method for maximum agreement over Boolean monomials, improving on the earlier work of Goldberg and Shan (2007). In particular, we develop a tighter upper bounding function and an improved branching procedure that exploits knowledge of the bound and the dataset, while having a lower branching factor. Experimental results show that the new method is able to solve larger problem instances and runs faster within a linear programming boosting procedure applied to medium-sized datasets from the UCI repository.
Citation
RUTCOR Research Report #14-2009, Rutgers Center for Operations Research, 640 Bartholomew Rd, Piscataway, NJ 08854, USA, October 2009.