A NEW IMPLICIT ENUMERATION SCHEME FOR THE DISCRIMINANT-ANALYSIS PROBLEM

This paper addresses, from a mathematical programming point of view, t he problem that consists in determining an hyperplane that separates, as well as possible, two finite sets of points in R(n). In our formula tion, a best separation hyperplane minimizes the number of misclassifi ed points. A new mixed integer formulation of this problem is proposed , together with a solution procedure based on implicit enumeration. Th e formulation is characterized by a small integrality gap. Extensive n umerical results on large scale problems (up to 300 points) are given for both the exact algorithm and a derived heuristic procedure.