An iterative mixed integer programming method for classification accuracy maximizing discriminant analysis

Linear discriminant functions which maximize the number of correctly classified observations in a training sample can be generated by a mixed integer programming (MIP) discriminant analysis model in which a binary variable is associated with each observation, but because of the computational requirements this model can only be applied to relatively small problems. In this paper, an iterative MIP method is developed to allow classification accuracy maximizing discriminant functions to be generated for problems with many more observations than can be considered by the standard MIP formulation. Using minimization of the sum of deviations as the objective, a mathematical programming discriminant analysis model is first used to generate a discriminant function for the complete set of observations. A neighborhood of observations about this function is then defined and an MIP model is used to generate a discriminant function that maximizes classification accuracy within this neighborhood. The process of defining a neighborhood about the most recently generated discriminant function and solving a neighborhood MIP model is repeated until there is no improvement in the total number of observations classified correctly. This new iterative MIP method is applied to a two-group problem involving 690 observations.