BLOCK PLACEMENT WITH A BOLTZMANN MACHINE

The Boltzmann Machine is a neural model based on the same principles of Simulated Annealing that reaches good solutions, reduces the computational requirements, and is well suited for a low-cost, massively parallel hardware implementation. In this paper we present a connectionist approach to the problem of block placement in the plane to minimize wire length, based on its formalization in terms of the Boltzmann Machine. We detail the procedure to build the Boltzmann Machine by formulating the placement problem as a constrained quadratic assignment problem and by defining an equivalent 0-1 programming problem. The key features of the proposed model are: 1) high degree of parallelism in the algorithm, 2) high quality of the results, often near-optimal, and 3) support of a large variety of constraints such as arbitrary block shape, flexible aspect ratio, and rotations/reflections. Experimental results on different problem instances show the skills of the method as an effective alternative to other deterministic and statistical techniques.