MAkE: Multiobjective algorithm for k-way equipartitioning of a point set

The classical problem of partitioning a given set of points, has applications in several areas such as facility location, scattered network, and in hierarchical design of VLSI circuits. While equipartitioning is traditionally associated with the single objective of minimum cutcost, the above application areas appear to demand more. In this paper, we introduce the problem of multiobjective k-way equipartitioning of a point set. Brief discussions on the above applications are followed by their generic formulation as a multiobjective k-way equipartitioning problem of a given point set. The non-commensurate multiobjective criteria addressed include (i) minimizing overall areas of the partitions, (ii) maximizing area of the individual partitions, (iii) minimizing the total compactness of the partitions, and (iv) minimizing the total geometric diversity of the obtained partitions. Since this optimization problem is computationally expensive in time and space, a technique based on genetic algorithm is proposed in order to obtain high quality results. Crossover and mutation operators specific to the k-way equipartitioning problem, have been designed and a new greedy operator named compaction is proposed to accelerate convergence. To illustrate the utility of the proposed formulation and the algorithm, a problem in VLSI layout design is considered. Results on synthetic data sets as well as those extracted from layouts of benchmark circuits demonstrate the effectiveness of the proposed multiobjective approach.