An integer programming approach for the 2-class single-group classification problem

MANUELA BLAUM; RICARDO C. CORRÊA; IVO KOCH; JAVIER MARENCO; MARCELO MYDLARZ

Congreso; X Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019); 2019

Two sets X B , X R ⊆ R d are linearly separable if the convex hulls of X B and X R are disjoint, hence there exists a hyperplaneseparating X B from X R . Such a hyperplane provides a method for classifying new points, according to which side of the hyperplanethe new points lie. In this work we consider a particular case of the 2-class classification problem, which asks to select the maximumnumber of points from X B and X R in such a way that the selected points are linearly separable. We present an integer programmingformulation for this problem, explore valid inequalities for the associated polytope, and develop a cutting plane approach.