Welcome to the Wiki of COPhy
In this wiki, we introduce the basic concepts of the combinatorial optimization methods that we use in our Combinatorial Optimization in Physics project (COPhy). More information can be found in our publications and on our project website.
The outline of the wiki is as follows:
<categorytree hideroot="on" mode="pages" showcount="on">COPhy</categorytree>
The Preliminaries category summarizes basic concepts such as graphs, matchings, flows, etc.
One focus of our work lies in the computation of optimum solutions for maximum cut problems (max-cut). In general, max-cut is NP-hard, and so we use a branch-and-cut algorithm for solving it. For planar graphs, however, the problem is polynomially solvable via a reduction to an appropriate matching problem. Prominent applications for the max-cut problem are the determination of exact ground states of Ising spin glasses. The corresponding articles can be found in category Max-cut.
The category on 2D Ising spin glasses focuses on the polynomially-solvable max-cut instances as they appear in the physics application.
The category Hard spin glasses deals with the general NP-hard variants of max-cut, also with a focus on the physics application.
If the spins are allowed to attain more than two states, say k, exact ground-state determination of the so-called Potts model amounts to solving a maximum-k-cut in the graph of interactions. Details can be found in categories Potts spin glasses and Max-k-cut.
If the number of spin states is large, the dominant term in the partition function for Potts glasses can be calculated by optimizing a specific submodular function. The latter can be done via iterated minimum-cut calculations. This is summarized in category Potts spin glasses (many states).
Finally, the Bernasconi model is a model for glasses without quenched disorder. Exact ground states can be determined by optimizing a polynomial of degree four which we do with a branch-and-bound approach. Category Bernasconi model explains more details.
The Bibliography lists a lot of relevant papers and articles.