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}]

Improve this question
$\endgroup$
4
  • 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.
    Commented Jul 16, 2014 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
    Commented Jul 16, 2014 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.
    Commented Apr 28, 2016 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
    Commented Apr 28, 2016 at 11:38

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Jul 21, 2014 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
    Commented Jul 21, 2014 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
    Commented Jul 22, 2014 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
    Commented Jul 22, 2014 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
    Commented Jul 22, 2014 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}$$

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .