The widely used Support Vector Machine (SVM) method has shown to yield good results in Supervised Classification problems. The Binarized SVM (BSVM) is a variant which is able to automatically detect which variables are, by themselves, most relevant for the classifier. In this work, we extend the BSVM introduced by the authors to a method that, apart from detecting the relevant variables, also detects the most relevant interactions between them. The classification ability of the proposed method is comparable to standard SVM for different kernels and clearly better than Classification Trees. Our method involves the optimization of a Linear Programming problem with a large number of decision variables, for which we use the well-known Column Generation technique.