# Category:COPhy

## Welcome to the Wiki of COPhy

In this wiki, we introduce the basic concepts of the combinatorial
optimization methods that we use in our **C**ombinatorial **O**ptimization in
**Phy**sics project (**COPhy**). More information can be found in our
publications and on our project website.

The outline of the wiki is as follows:

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.

## Subcategories

This category has the following 8 subcategories, out of 8 total.

## 1## 2 |
## 2 cont.## 3 |
## 3 cont. |