<p>Have a look at the paper "Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem" by Alain Billionnet and Sourour Elloumi. They mention there that the binary quadratic problem </p>

<p>$$\min \left\{ x^T Q x + c^Tx : x \in \{0,1\}^n \right\},$$</p>

<p>where $Q$ is a symmetric matrix with diagonal entries all zero, is equivalent to the mixed integer linear programming problem</p>

<p>$$
\begin{array}{cccc}
\min &amp; \sum_{i} c_i x_i + \sum_{i &lt; j} 2Q_{ij} y_{ij} \\
\text{s.t.} 
&amp;  y_{ij} \leq x_i &amp; i &lt; j, &amp; Q_{ij} &lt; 0 \\
&amp;  y_{ij} \leq x_j &amp; i &lt; j, &amp; Q_{ij} &lt; 0 \\
&amp;  y_{ij} \geq x_i + x_j - 1 &amp; i &lt; j, &amp; Q_{ij} &gt; 0 \\
&amp;  y_{ij} \geq 0 &amp; i &lt; j, &amp; Q_{ij} \neq 0\\
&amp;  x_i \in \{0, 1\}.
\end{array}
$$</p>

<p>Since you are interested in solving the Ising spin state problem, you should also check out the chapter "Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut" by Frauke Liers, Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi.</p>

<p>Also check out the paper "Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations" by Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele that describes the semidefinite based branch-and-bound software <a href="http://biqmac.uni-klu.ac.at" rel="nofollow">Biq Mac</a> and its performance on solving Ising spin state problems.</p>

<p>Finally, you can try <a href="http://lipn.univ-paris13.fr/BiqCrunch/" rel="nofollow">BiqCrunch</a> which is another semidefinite based branch-and-bound solver that is capable of solving Ising spin state problems.</p>

CC BY-SA 3.0
2015-03-28T21:50:02.970Z
2015-03-28T21:50:02.970Z
Nathan Krislock
<p>I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem)</p>

<p>$$
maximise: \sum J_{ij}S_{i}S_{j}
$$
$$
-1\leq J_{ij} \leq 1
$$
$$
S_{i},S_{j} \epsilon (-1,1)
$$
Value of $J_{ij}$ is given.
The goal is to find optimal values of $S_{i}$ to maximise the value. 
For ex:
$J_{12}=1, J_{13}=-1, J_{23}=-1$. One of the solutions for maximum energy is 3 with $S_{1}=1, S_{2}=1, S_{3}=-1$.</p>

<p>I am finding it difficult to convert this into integer linear program.</p>

<p>This is my initial approach for the conversion.
I tried to take an aditional variable $X_{i}$ and convert this program as
$$
maximise: \sum X_{i}
$$
$ if((S_{i}=-1 or S_{j}=-1) and J_{ij}=-1) \implies X_{i}=1 $
$ if((S_{i}=-1 or S_{j}=-1) and J_{ij}=1) \implies X_{i}=-1 $
$ if((S_{i}=-1 and S_{j}=-1) and J_{ij}=-1) \implies X_{i}=-1 $
$ if((S_{i}=-1 and S_{j}=-1) and J_{ij}=1) \implies X_{i}=1 $</p>

<p>I dont know if this approach is correct or not. Even i dont know how to convert this to linear program.
Any suggestion or help is greatly appreciated.</p>

CC BY-SA 3.0
2015-03-28T17:13:24.073Z
It's a binary quadratic program, not a binary linear program.
Michael Grant
CC BY-SA 3.0
2015-03-28T17:38:21.003Z
I am trying to find the ground state using lp_solve. lp_solve cannot handle Quadratic terms. Is there any way to convert this problem into a linear program.
77H3jjuu
CC BY-SA 3.0
2015-03-28T18:52:22.780Z
Ah, I see now. Normally I would say "of course not!" but the fact that every single quantity is $\pm 1$ suggests I had better reserve judgement.
Michael Grant
CC BY-SA 3.0
2015-03-28T22:41:38.507Z
I do think the other commenters are right. The right way to solve this is using a binary quadratic programming engine. However I do know that it is possible to convert this to a mixed integer linear program, and when I get home and finish editing my answer I will post it.
Michael Grant
CC BY-SA 3.0
2015-03-29T00:20:36.257Z
I posted an answer [here](http://math.stackexchange.com/a/1210586/52878).
Michael Grant
<linear-algebra><linear-programming><integer-programming>
convertion into integer linear program for Ising spin state problem
77H3jjuu
# convertion into integer linear program for Ising spin state problem

(Asked by: username_0 on 2015-03-28)

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp\_solve. (This is just a miniature version of Ising state problem)

$$
maximise: \sum J\_{ij}S\_{i}S\_{j}
$$
$$
-1\leq J\_{ij} \leq 1
$$
$$
S\_{i},S\_{j} \epsilon (-1,1)
$$
Value of $J\_{ij}$ is given.
The goal is to find optimal values of $S\_{i}$ to maximise the value.
For ex:
$J\_{12}=1, J\_{13}=-1, J\_{23}=-1$. One of the solutions for maximum energy is 3 with $S\_{1}=1, S\_{2}=1, S\_{3}=-1$.

I am finding it difficult to convert this into integer linear program.

This is my initial approach for the conversion.
I tried to take an aditional variable $X\_{i}$ and convert this program as
$$
maximise: \sum X\_{i}
$$
$ if((S\_{i}=-1 or S\_{j}=-1) and J\_{ij}=-1) \implies X\_{i}=1 $
$ if((S\_{i}=-1 or S\_{j}=-1) and J\_{ij}=1) \implies X\_{i}=-1 $
$ if((S\_{i}=-1 and S\_{j}=-1) and J\_{ij}=-1) \implies X\_{i}=-1 $
$ if((S\_{i}=-1 and S\_{j}=-1) and J\_{ij}=1) \implies X\_{i}=1 $

I dont know if this approach is correct or not. Even i dont know how to convert this to linear program.
Any suggestion or help is greatly appreciated.

**Tags:** linear-algebra, linear-programming, integer-programming

> **Comments:**
> **username_1**: It's a binary quadratic program, not a binary linear program.  
> **username_0**: I am trying to find the ground state using lp_solve. lp_solve cannot handle Quadratic terms. Is there any way to convert this problem into a linear program.  
> **username_1**: Ah, I see now. Normally I would say "of course not!" but the fact that every single quantity is $\pm 1$ suggests I had better reserve judgement.  
> **username_1**: I do think the other commenters are right. The right way to solve this is using a binary quadratic programming engine. However I do know that it is possible to convert this to a mixed integer linear program, and when I get home and finish editing my answer I will post it.  
> **username_1**: I posted an answer [here](http://math.stackexchange.com/a/1210586/52878).  

---

## 1 answers

### Answer by username_2 on 2015-03-28. Score: 2

Have a look at the paper "Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem" by Alain Billionnet and Sourour Elloumi. They mention there that the binary quadratic problem

$$\min \left\{ x^T Q x + c^Tx : x \in \{0,1\}^n \right\},$$

where $Q$ is a symmetric matrix with diagonal entries all zero, is equivalent to the mixed integer linear programming problem

$$
\begin{array}{cccc}
\min & \sum\_{i} c\_i x\_i + \sum\_{i < j} 2Q\_{ij} y\_{ij} \\
\text{s.t.}
& y\_{ij} \leq x\_i & i < j, & Q\_{ij} < 0 \\
& y\_{ij} \leq x\_j & i < j, & Q\_{ij} < 0 \\
& y\_{ij} \geq x\_i + x\_j - 1 & i < j, & Q\_{ij} > 0 \\
& y\_{ij} \geq 0 & i < j, & Q\_{ij} \neq 0\\
& x\_i \in \{0, 1\}.
\end{array}
$$

Since you are interested in solving the Ising spin state problem, you should also check out the chapter "Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut" by Frauke Liers, Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi.

Also check out the paper "Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations" by Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele that describes the semidefinite based branch-and-bound software [Biq Mac](http://biqmac.uni-klu.ac.at) and its performance on solving Ising spin state problems.

Finally, you can try [BiqCrunch](http://lipn.univ-paris13.fr/BiqCrunch/) which is another semidefinite based branch-and-bound solver that is capable of solving Ising spin state problems.


---

