Spin glass ground stateProblemSpin 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. InputA 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.OutputLocal Search
Assignment for variables n1, n2... n1 = 1; n2 = -1; n3 = 1; Linear program
Assignment for variables n1, n2... SAT
Assignment for boolean variables n1,n2.. Example instancesAn instance with minimum energy of -17An 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. |