Assignment round three

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.

Assignment

Create a Java program that encodes the optimization problem instance as a linear program in the format described in lpformat.html. Then use the java-utility lp.ToLPSolve found in hoa.jar to convert it to format accepted by lp_solve and use lp_solve to solve the instance. See the general information page for an example on how to use the tools. Note that lp.ToLPSolve tool does not preserve the value of the objective function as lp_solve does not support constant terms in it. Objective function is also converted into a maximisation version. You can circumvent this by creating an additional variable which has the same value as the objective function or, if you know the optimal value, you can add a constraint objectivefunction = optimal value; Alternatively you can create a new variable objectivevalue and a constrait objectivevalue= objectivefunction

Test your solution with two sets of instances (optimal energy is in the file name): set 1 set 2. For each set, test how many can be solved in 10 minutes with lp_solve and what is the average and median time.

Input

The program will be run with command

java SpinGlass <graph>

Output

After running java SpinGlass <graph> | java lp.ToLPSolve | lp_solve | java lp.FromLPSolve:
Assignment for variables n1, n2...
n1 = -1; if site n1 has value -1
n2 = 1; if site n2 has value 1
(The output can of course have your own extra variables in addition to these) .
Note: lp_solve does not support negative values for variables. Declare integers that can have negative variables as "signed int" instead of "int". ToLPSolve then splits them and FromLPSolve combines them.

Deliverable

Return the commented source code and a small report describing your approach and results for the test sets to airusane(at)tcs.hut.fi.

Grading

Correct solution on first try with sufficient report earns 3 points, each failed attempt decreasing points by 1. Submitted solutions are compared with each other and a reference solution. Good solutions are granted 1-2 extra points.

Example instances