Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model

Solution methods are presented for a mixed-integer program (MIP) associated with a method for constrained discrimination. In constrained discrimination, one wishes to maximize the probability of correct classification subject to intergroup misclassification limits. The misclassification limits are satisfied by allowing the placement of observations in a reserved judgment group. The approach investigated here involves modifying a standard classification rule by solving an optimization problem. A polynomial-time algorithm for solving the problem is given for two-group discrimination. The decision problem upon which the optimization problem is based is shown to be NP complete for a general number of groups. For three or more groups, an MIP is used to solve the problem. Solution methods incorporating cutting planes from conflict graphs are presented for solving instances in a branch-and-bound framework. These methods are used to enhance industry-standard software, and are shown to provide as much as a 20-fold reduction in computational time over the software alone. Computational experiments illustrate the tradeoff between misclassification rates and reserved judgment rates. Some base classifiers are not well suited to be modified to a constrained discrimination rule. The method for constrained discrimination studied here performs particularly well in the presence of class imbalance. For certain other data sets, however, the method is outperformed by a simple centroid method.