An Integer Programming Approach for the 2-class Single-group Classification Problem
Ricardo Cordeiro Correa, Manuela Blaum, Javier L. Marenco, Ivo Koch, Marcelo Mydlarz · Electronic Notes in Theoretical Computer Science · 2019
Two sets X B , X R ⊆ R d are linearly separable if their convex hulls are disjoint, implying that a hyperplane separating X B from X R exists. Such a hyperplane provides a method for classifying new points, according to the side of the hyperplane in which the new points lie. In this work we consider a particular case of the 2-class classification problem, which asks to select the maximum number of points from X B and X R in such a way that the selected points are linearly separable. We present an integer programming formulation for this problem, explore valid inequalities for the associated polytope, and develop a cutting plane approach coupled with a lazy-constraints scheme.