New Methods for the Construction of Test Cases for Partitioning Heuristics

Partitioning is an important problem in the design automation of integrated circuits. This problem in many of its formulation is NP-Hard, and several heuristic methods have been proposed for its solution. To evaluate the effectiveness of the various partitioning heuristics, it is desirable to have test cases with known optimal solutions that are as “random looking” as possible. In this paper, we describe several methods for the construction of such test cases. All our methods except one use the theory of network flow. The remaining method uses a relationship between a partitioning problem and the geometric clustering problem. The latter problem can be solved in polynomial time in any fixed dimension.