×

An application of combinatorial optimization to statistical physics and circuit layout design. (English) Zbl 0646.90084

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.

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
PDFBibTeX XMLCite
Full Text: DOI Link