Optimization Online


An Improved Branch-and-Bound Method for Maximum Monomial Agreement

Eckstein Eckstein(jeckstei***at***rci.rutgers.edu)
Noam Goldberg(noamgold***at***tx.technion.ac.il)

Abstract: 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.

Keywords: branch-and-bound, monomials, maximum agreement, machine learning, Boolean functions

Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: RUTCOR Research Report #14-2009, Rutgers Center for Operations Research, 640 Bartholomew Rd, Piscataway, NJ 08854, USA, October 2009.

Download: [PDF]

Entry Submitted: 11/08/2009
Entry Accepted: 11/08/2009
Entry Last Modified: 11/08/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society