An application of combinatorial optimization to statistical physics and circuit layout design

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