next up previous
Next: The Traveling Salesman Up: Examples of Optimization Previous: Graph Partitioning

A Graph Problem Disguised as a Spin Model

Introduce a variable which is +1 if the element is on the first chip, and -1 if it is on the second. Introduce a connectivity matrix if i and j are connected, 0 otherwise.

The penalty for connections between chips is

We want roughly the same number of elements in chip 1 and chip 2 , so we want to make as close as possible to zero. Can do this by adding a penalty term to the cost function

The problem now looks like an Ising spin glass! As we might expect, SA works well for this problem.



Paul Coddington, Northeast Parallel Architectures Center at Syracuse University, paulc@npac.syr.edu