An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

TLDR

These problems arise in solid‑state physics (spin glasses) and in VLSI/PCB design (minimizing vias). We study the ground‑state problem for spin glasses with external magnetic field and the via‑minimization problem under pin preassignments and layer preferences. Both problems are reduced to graph max‑cut, and we develop a cutting‑plane algorithm based on a partial characterization of the cut polytope. The algorithm solves max‑cut instances with up to 1,600 nodes.

Abstract

We study the problem of finding ground states of spin glasses with exterior magnetic field, and the problem of minimizing the number of vias (holes on a printed circuit board, or contacts on a chip) subject to pin preassignments and layer preferences. The former problem comes up in solid-state physics, and the latter in very-large-scale-integrated (VLSI) circuit design and in printed circuit board design. Both problems can be reduced to the max-cut problem in graphs. Based on a partial characterization of the cut polytope, we design a cutting plane algorithm and report on computational experience with it. Our method has been used to solve max-cut problems on graphs with up to 1,600 nodes.