Groupe d’études et de recherche en analyse des décisions

G-93-32

A New Implicit Enumeration Scheme for the Discriminant Analysis Problem

, et

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.

, 22 pages

Ce cahier a été révisé en mars 1994