Integer Programming Solution of a Classification Problem

A classification problem is presented in which it is desired to assign a new individual or observation with k characteristics to one of two distinct populations based upon historical sets of samples from the two populations. The resulting classification problem is formulated as a mixed-integer programming problem. The solution, which can be obtained through use of a partitioning algorithm based on Benders decomposition, provides a nonparametric classification statistic which minimizes the expected total cost of misclassification. Also, an enumeration algorithm is developed for the special case of k = 2. Monte Carlo studies are reported which compare the results of the enumeration algorithm with Anderson's "normal" procedure for different underlying distributions. The performance of the enumeration algorithm is shown to be significantly better than Anderson's normal procedure for distributions with uncorrelated normal populations with unequal covariance matrices and for uncorrelated skewed populations with equal covariances.