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.
As pointed out in the other thread, it really would be best to solve this using a binary quadratic programming engine. Nevertheless, it can indeed be converted to a binary linear program.
Consider this equation: $$\bar{S}_i + \bar{S}_j = 2 X_{ij} + Y_{ij}$$ where $X_{ij},Y_{ij}\in\{0,1\}$ and $$\bar{S}_i = (1-S_i)/2 = \begin{cases} 1 & S_i = -1 \\ 0 & S_i = +1 \end{cases} \qquad i=1,2,\dots, n.$$ Then $Y_{ij}=0$ if $S_i=S_j$ and $Y_{ij}=1$ if $S_i\neq S_j$, and $$S_i S_j = (-1)^{\bar{S}_i+\bar{S}_j} = 1 - 2Y_{ij}.$$ Note that if $i=j$, $S_iS_j=1$, so the corresponding $J_iS_iS_j$ term is a constant that will not change the optimal result. So we need only consider the $i\neq j$ cases. Therefore, we have this: \begin{array}{lll} \text{maximize} & \sum_{i,j:~i\neq j,~J_{ij}\neq 0} J_{ij}(1 - 2 Y_{ij}) \\ \text{subject to} & \bar{S}_i + \bar{S}_j = 2 X_{ij} + Y_{ij} & i,j:~i\neq j,~J_{ij}\neq 0\\ & \bar{S}_i\in\{0,1\} & i=1,2,\dots, n \\ & X_{ij},Y_{ij}\in\{0,1\} & i,j:~i\neq j,~J_{ij}\neq 0 \\ \end{array} The problem here is that we have created $2n^2-2n$ new binary variables to accomplish this, or $n^2-n$ if $J_{ij}=J_{ji}$. This is likely to be more costly than just using a binary quadratic programming engine.