Market segmentation is a core marketing concept that is conceptually simple to define and understand, but inherently a multi-criteria problem that is hard to measure and computationally difficult in many aspects. This paper reviews the development of market segmentation techniques and identifies the computational issues of the applications of market segmentation. A multidimensional unified framework for market segmentation is proposed based on the relationship among segmentation variables, data measures, and the multi-objective optimization techniques implemented. We conduct an empirical comparison of two prominent methods: a concomitant finite mixture model and a multi-objective evolutionary algorithm. The result shows that the proposed framework helps to understand different segmentation models and solutions and to guide the development of new market segmentation solution techniques