An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

Francisco Barahona, Martin Grötschel, Michael Jünger and Gerhard Reinelt
Additional contact information
Francisco Barahona: University of Waterloo, Ontario, Canada
Martin Grötschel: Universitat Augsburg, Augsburg, West Germany
Michael Jünger: Universitat Augsburg, Augsburg, West Germany
Gerhard Reinelt: Universitat Augsburg, Augsburg, West Germany

Operations Research, 1988, vol. 36, issue 3, 493-513

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 (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.3.493 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:36:y:1988:i:3:p:493-513

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().