One of the steps in the design process of chips is the positioning of every single component or 'cell' on the chip. The cells are mutually connected by wires. The wiring scheme is given, and in this phase of the design process the positioning of the various cells must be determined. Some (relatively few) cells have a prescribed position.

For the classical positioning problem one considers the chip as a two-dimensional plane; the cells are modelled by rectangles of various sizes. The positioning has to satisfy some conditions:

1. the cells must be placed within a certain rectangle (core area)
2. cells are not allowed to overlap
3. the total wire length must be minimized.

The problem becomes more difficult when large parts of the core area are excluded from positioning, often caused by large, functional components that were placed beforehand (one could think of memory, or components that are designed by other companies). The remaining 'free area' within the core area is usually comparable to a cheese with holes, or 'holey cheese'. Obviously, the cells cannot be placed on the blockages, and this additional requirement makes the positioning problem significantly harder.

The picture shows an example of a typical 'holey chees'. The green areas are allowed, the white ones are blocked. (The 'noise' in the green areas has nothing to do with the free space.) Note that the free area is strongly disconnected.

The current algorithmes of Magma DA suffice for more or less convex areas. However, in 'holey cheeses' they often end up in local minima that are far from optimal.

Question:
How can Magma DA find good solutions in case of holey cheeses?