BLOCK PLACEMENT WITH A BOLTZMANN MACHINE

The Boltzmann Machine is a neural model based on the same principles o f Simulated Annealing that reaches good solutions, reduces the computa tional requirements, and is well suited for a low-cost, massively para llel hardware implementation. In this paper we present a connectionist approach to the problem of block placement in the plane to minimize w ire length, based on its formalization in terms of the Boltzmann Machi ne. We detail the procedure to build the Boltzmann Machine by formulat ing the placement problem as a constrained quadratic assignment proble m and by defining an equivalent 0-1 programming problem. The key featu res of the proposed model are: 1) high degree of parallelism in the al gorithm, 2) high quality of the results, often near-optimal, and 3) su pport of a large variety of constraints such as arbitrary block shape, flexible aspect ratio, and rotations/reflections. Experimental result s on different problem instances show the skills of the method as an e ffective alternative to other deterministic and statistical techniques .