1988/06/01 by Francisco Barahona, Martin Grötschel, Michael Jünger +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Printed circuit board #Very-large-scale integration #Computer science #Chip #Circuit design #Ground plane #Maximum cut #Combinatorial optimization #Mathematical optimization #Algorithm #Mathematics #Theoretical computer science #Graph #Telecommunications #Embedded system
paper · doi:10.1287/opre.36.3.493
openalex publication_date 1988/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
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.