# enhancing a MIP formulation of Ising model [closed]

I want to construct a MIP formulation for Ising model. For simplicity, I will only include terms involving nearest-neighbor pairs and triangular terms. I propose one formulation and ask whether there would be some stronger formulation form that would be potentially faster in computation. 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}]

• A few comments: you can condense the bounded, integral constraints by just writing, for instance, $s_{i,j} \in \{0,1\}$. This construction is common in mixed integer programs. Also, I'm vaguely familiar with the Ising model; the meaning of decision variables in the formulation is not clear; please clarify. For instance, presumably, you want $s_{i, j}$ to be spins, but the spins of lattice sites are $\pm 1$, so if $s_{ij}$ is supposed to be the spin of lattice site $(i,j)$, then its term in the energy should be $2s_{ij} - 1$ (which is $-1$ and $1$ when $s_{ij}$ is $0$ and $1$, respectively). Jul 14, 2014 at 7:44
• Thank you very much for your comment. Actually, the spin variable could be 0,1 too and it's equivalent to the -1,1 formulation by change of the objective vector. Thank you:D Jul 14, 2014 at 13:25
• I know; my comment explicitly constructs the correspondence. What I am saying here is that your formulation is unclear, and the way you have described your problem requires considerable effort on the part of readers to make any progress. Jul 14, 2014 at 18:36
• noted:D thank you very much for your comment:D Jul 14, 2014 at 19:55
• mathoverflow.net/q/176057/37212. 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.
– D.W.
Apr 28, 2016 at 5:10