A mixed integer linear model for clustering with variable selection

Stefano Benati, Sergio Garcia

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)280-285
Number of pages6
JournalComputers and Operations Research
Publication statusPublished - 2014


  • Clustering
  • p-median
  • Variable selection
  • Radius formulation


Dive into the research topics of 'A mixed integer linear model for clustering with variable selection'. Together they form a unique fingerprint.

Cite this