Pre-partitioning as a means of enhancing pairwise interchange solutions to quadratic assignment problems

Two partition/interchange processes are described for solving quadratic assignment problems. Explicit partitioning is used in both methods to decompose the initial large graph into several smaller graphs for initial placement and subsequent interchange optimization. Comparative runs were made between the two processes and against the interchange process without partitioning on problems involving up to 100 vertices. The comparative results clearly establish the effectiveness of partitioning in enhancing the performance of interchange processes and provide a basis for selecting partitioning processes.While the two methods described herein were developed for microcircuit placement problems, they are applicable to quadratic assignment problems arising from numerous other settings.