A local optimization-based solution to the rectangle layout problem

In this paper we apply a family of heuristics to solve the rectangle layout problem. Our principal technique, however, is a variant of local optimization. This technique, which we call sacrificing, differs from the traditional local optimization algorithm in two respects. Firstly, we relax the monotonicity requirement by permitting intermediate solutions that are not the best seen to date; secondly, we expand the notion of neighbourhood to include families of solution perturbation schemes. We solve a problem by combining these simple transformations into a high-level program with sacrificing our key transformation. We demonstrate the effectiveness of our approach on a number of test cases.