A mixed integer linear model for clustering with variable selection

This paper introduces an extension of the p-median problem in which the distance function between units is calculated as the distance sum on the q most important variables out of a set of size m. This model has applications in cluster analysis (for example, in sociological surveys), where analysts have a large list of variables available for inclusion, but only a subset of them (true variables) is appropriate for uncovering the cluster structure. Therefore, researchers must carefully separate the true variables from the other before computing data partitions. Here we show that this problem can be formulated as a mixed integer non-linear optimization model where clustering and variable selection are done simultaneously. Then we provide two different linearizations and compare their performance with the default method of clustering with all the variables (which is a p-median model) on a set of artificially generated binary data, showing that the model based on a radius formulation performs the best.