New perspectives in VLSI design automation: deterministic packing by Sequence Pair

In the paper we consider a problem of packing rectangular blocks on a plane, which is known as Block Packing Problem (BPP). This problem is a central issue of the modern VLSI chips design methods. Basing on a new interpretation of the Sequence-Pair representation of the packing solution-space, which is based on Complementary Mirror Constraint Graphs (CMCG), we develop the efficient method of neighborhood exploration. This method might be able to improve the efficiency of other neighborhood-based search methods, such as simulated annealing or tabu search, as well as, to construct efficient heuristics. We illustrate application of the developed method by constructing a heuristic algorithm for solving BPP and comparing its efficiency and effectiveness to the algorithms commonly used so far.