A local optimization-based solution to the rectangle layout problem

This paper applies a family of heuristics to solve the rectangle layout problem. The principal technique, however, is a variant of local optimization. This technique, which is called sacrificing, differs from the traditional local optimization algorithm in two respects. Firstly, it relaxes the monotonicity requirement by permitting intermediate solutions that are not the best seen to date; secondly, it expands the notion of neighbourhood to include families of solution perturbation schemes. The paper solves a problem by combining these ssimple transformations into a high-level program with sacrificing the key transformation. It demonstrates the effectiveness of the approach on a number of test cases.