TCS / Studies / T-79.4201 / Home Assignments / Thispage
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Spin glass ground state

Problem

Spin glass models are widely used in physics to model the microscale properties of materials and other complex systems. Formally, an "Ising (+/-1) spin glass" consists of n (+/-1)-valued binary variables ("sites") s_1,...s_n. Each pair of sites i, j are connected by an "interaction coefficient" J_{ij}, which may take on values +1, -1, or 0. A given system of interactions J defines an "energy" function on the spin configurations as:


    E(s_1,...s_n) = - sum_{ij} J_{ij} s_i s_j.

A "ground state" for a given system of interactions J is a configuration of the spin values achieving a minimum of the energy function E = E_J. (Intuitively, two positively interacting spins "want" to be in the same state, and two negatively interacting spins "want" to be in opposite states. The goal is to find a configuration of the spins satisfying as many of these "wishes" as possible.) This is the optimization problem. In the decision problem the task is to find a ground state that has energy of at most a given bound K.

Input

A graph with each node representing a "site". An edge between two nodes has an attribute "interaction" which can have -1/0/+1 values and represents the interaction between the sites. In the decision problem, the second parameter is the maximum energy allowed.

Output

Local Search

Assignment for variables n1, n2...
n1 = -1; if site n1 has value -1
n2 = 1; if site n2 has value 1
Example output:

n1 = 1;
n2 = -1;
n3 = 1;

Linear program

Assignment for variables n1, n2...
n1 = -1; if site n1 has value -1
n2 = 1; if site n2 has value 1
Note: lp_solve does not support negative values for variables. Declare integers that can be negative as "signed int" instead of "int". ToLPSolve then splits them and FromLPSolve combines them.

SAT

Assignment for boolean variables n1,n2..
n1 = 0 if site n1 has value -1
n2 = 1 if site n2 has value 1

Example instances

An instance with minimum energy of -17
An instance with minimum energy of -43
An instance with minimum energy of -48

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 25 March 2006.