Mathematical Models for Feature Selection and their Application to Bioinformatics

In this paper, we consider an Integer Programming (IP) model for a particular class of Feature Selection (FS) problems. FS arises in Data Analysis and Data Mining to properly reduce the dimension of the space where the data are represented. Such dimensional reduction is performed to make the analysis tractable while retaining the largest amount of information. We describe such model exploiting some o its mathematical properties, show that an exact solution approach is out of the question for realistically large size data sets and analyze the performances of an ad-hoc developed randomized heuristics. Such method has already been applied successfully to solve real instances arising in computational biology; the experimental work proposed here is based on randomly generated instances designed with the scope of properly testing the solution method.