0
$\begingroup$

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN pair interaction and a "triangular" interaction term. The formulation I give is as followed. And I wish to ask for suggestions whether there would be some stronger formulation that could make computation faster. Thank you :D

the original objective is:

$$\sum\limits_{i = 1}^{29} {\sum\limits_{j = 1}^{30} {{J_1}{s_{i,j}}{s_{i + 1,j}}} } + \sum\limits_{i = 1}^{30} {\sum\limits_{j = 1}^{29} {{J_1}{s_{i,j}}{s_{i,j + 1}}} } + \sum\limits_{i = 1}^{29} {\sum\limits_{j = 1}^{29} {{J_3}{s_{i,j}}{s_{i + 1,j}}{s_{i,j + 1}}} } $$

$${s_{i,j}} \in \{ 0,1\} $$

we linearize it so that:

[\begin{align} & \min : \\ & \sum\limits_{i=1}^{29}{\sum\limits_{j=1}^{30}{{{J}_{1}}{{s}_{i,j,1}}}}+\sum\limits_{i=1}^{30}{\sum\limits_{j=1}^{29}{{{J}_{1}}{{s}_{i,j,2}}}}+\sum\limits_{i=1}^{29}{\sum\limits_{j=1}^{29}{{{J}_{3}}{{s}_{i,j,3}}}} \\ & \text{subject to:} \\ & \forall i=1...29\,j=1...30\,\ k=1...4 \\ & \left[ \begin{matrix} {{s}_{i,j}} \\ {{s}_{i+1,j}} \\ {{s}_{i,j,1}} \\ \end{matrix} \right]={{y}_{i,j,1,1}}\left[ \begin{matrix} 0 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,1,2}}\left[ \begin{matrix} 1 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,1,3}}\left[ \begin{matrix} 0 \\ 1 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,1,4}}\left[ \begin{matrix} 1 \\ 1 \\ 1 \\ \end{matrix} \right] \\ & \sum\limits_{k=1}^{4}{{{y}_{i,j,1,k}}=1} \\ & 0\le y\le 1 \\ & {{y}_{i,j,1,k}}\text{ is integral} \\ & \\ & \forall i=1...30\,j=1...29\,\,k=1...4 \\ & \left[ \begin{matrix} {{s}_{i,j}} \\ {{s}_{i,j+1}} \\ {{s}_{i,j,1}} \\ \end{matrix} \right]={{y}_{i,j,2,1}}\left[ \begin{matrix} 0 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,2,2}}\left[ \begin{matrix} 1 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,2,3}}\left[ \begin{matrix} 0 \\ 1 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,2,4}}\left[ \begin{matrix} 1 \\ 1 \\ 1 \\ \end{matrix} \right] \\ & \sum\limits_{k=1}^{4}{{{y}_{i,j,2,k}}=1} \\ & 0\le {{y}_{i,j,2,k}}\le 1 \\ & {{y}_{i,j,2,k}}\text{ is integral} \\ & \\ & \forall i=1...29\,j=1...29\,\,k=1...8 \\ & \left[ \begin{matrix} {{s}_{i,j}} \\ {{s}_{i+1,j}} \\ {{s}_{i,j+1}} \\ {{s}_{i,j,3}} \\ \end{matrix} \right]={{y}_{i,j,3,1}}\left[ \begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,2}}\left[ \begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,3}}\left[ \begin{matrix} 0 \\ 1 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,4}}\left[ \begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,5}}\left[ \begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,6}}\left[ \begin{matrix} 1 \\ 0 \\ 1 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,7}}\left[ \begin{matrix} 0 \\ 1 \\ 1 \\ 0 \\ \end{matrix} \right]+{{y}_{i,j,3,8}}\left[ \begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ \end{matrix} \right] \\ & \sum\limits_{k=1}^{8}{{{y}_{i,j,3,k}}=1} \\ & 0\le {{y}_{i,j,3,k}}\le 1 \\ & {{y}_{i,j,3,k}}\text{ is integral} \\ & \\ & \forall i=1...30\,j=1...30 \\ & 0\le {{s}_{i,j}}\le 1 \\ & {{s}_{i,j}}\quad \text{integral} \\ \end{align}]

$\endgroup$
  • 1
    $\begingroup$ You probably don't want to reinvent the wheel, especially when it comes to Ising model simulation. I would suggest looking at Metropolis (Monte Carlo) implementations or cluster algorithms like Swendsen/Wang. $\endgroup$ – Alex R. Jul 16 '14 at 16:48
  • $\begingroup$ Actually, we don't want to do monte carlo on spin systems. The problem for monte carlo is that, it could not give me the true ground state for certain and it could not provide an bound on how low energy the true ground state would possibly be. Thank you :D $\endgroup$ – user40780 Jul 16 '14 at 20:51
  • $\begingroup$ scicomp.stackexchange.com/q/14130/4274. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Apr 28 '16 at 5:10
  • $\begingroup$ I'm voting to close this question as off-topic because it was cross-posted and answered at another site. $\endgroup$ – Todd Trimble Apr 28 '16 at 11:38
1
+50
$\begingroup$

This problem is studied in Condensed Matter. You may wish to look at Projected Entangled Pair States - the 2D generalization of famous Density Matrix Renormalization Group / Matrix Product States ansatz. The recent development is reported in http://arxiv.org/abs/1405.3259 but do consider references therein as well.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So are they really solving exactly the same problem??? with decision variables being the spins and they are trying to minimizing over spin configurations (where spins can only be 0,1)??? Thank you very much:) $\endgroup$ – user40780 Jul 21 '14 at 22:24
  • 1
    $\begingroup$ They optimize over wavefunction, which is a linear combination of all possible states, $2^{30 \times 30}$ in your case. You seem to restrict this to pure states only. $\endgroup$ – Dmitry Savostyanov Jul 21 '14 at 23:55
  • $\begingroup$ Uhm... Interesting, I believe they include quadratic terms like s[1,1]*s[1,2], do they also include triplet terms like s[1,1]*s[1,2]*s[2,2]? It's rather difficult for me to infer from their equations, due to different background.... thank you very much :) $\endgroup$ – user40780 Jul 22 '14 at 13:47
  • 1
    $\begingroup$ They include pairwise interactions, but I doubt it comes to triples. Anyway, the PEPS technique itself is applicable to any interaction pattern. $\endgroup$ – Dmitry Savostyanov Jul 22 '14 at 13:55
  • 1
    $\begingroup$ The DMRG / MPS methods arose in quantum physics. The idea was unknown to Maths community for quite some time and was rediscovered under the name Tensor Trains. On this you may wish to check the intro and references in my recent paper 10.1016/j.cpc.2013.12.017 $\endgroup$ – Dmitry Savostyanov Jul 22 '14 at 14:27
0
$\begingroup$

Actually, one way I realize is to use this kind of constraints: $${s_i} + {s_j} - 1 \le {s_i}*{s_j} \le {s_i}$$

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.