This paper addresses, from a mathematical programming point of view, the problem that consists in determining an hyperplane that separates, as well as possible, two finite sets of points in Rn. In our formulation, a best separation hyperplane minimizes the number of misclassified points. A new mixed integer formulation of this problem is proposed, together with a solution procedure based on implicit enumeration. The formulation is characterized by a small integrality gap. Extensive numerical results on large scale problems (up to 300 points) are given for both the exact algorithm and a derived heuristic procedure.
Paru en septembre 1993 , 22 pages
Ce cahier a été révisé en mars 1994