An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt
Operations Research · 1988 · Volume 36 · Issue 3
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.
Keywords
432 the max-cut polytope, 628 a cutting plane method for the max-cut problem, 633 applications of integer programming to physics and VLSI design
Enable JavaScript for citation tools and additional paper interactions.