Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard An application of combinatorial optimization to statistical physics and circuit layout design. (English) Zbl 0646.90084 Oper. Res. 36, No. 3, 493-513 (1988). 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 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. Cited in 117 Documents MSC: 90C35 Programming involving graphs or networks 90C06 Large-scale problems in mathematical programming 65K05 Numerical mathematical programming methods 90C90 Applications of mathematical programming 90C27 Combinatorial optimization Keywords:ground states of spin glasses; solid-state physics; circuit design; printed circuit board design; max-cut problem in graphs; cutting plane algorithm PDFBibTeX XMLCite \textit{F. Barahona} et al., Oper. Res. 36, No. 3, 493--513 (1988; Zbl 0646.90084) Full Text: DOI Link