2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Geoff Oxberry Jul 14 '14 at 7:44
  • $\begingroup$ 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 $\endgroup$ – user40780 Jul 14 '14 at 13:25
  • $\begingroup$ 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. $\endgroup$ – Geoff Oxberry Jul 14 '14 at 18:36
  • $\begingroup$ noted:D thank you very much for your comment:D $\endgroup$ – user40780 Jul 14 '14 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 28 '16 at 5:10
1
$\begingroup$

Generally speaking, you want to construct formulations such that the convex hull of the linear programming (LP) relaxation is as small as possible, while retaining all potentially optimal feasible solutions. (Of course, feel free to write constraints that exclude currently feasible solutions that are known to be suboptimal.) In the ideal case, this convex hull has integral extreme points, in which case, the integrality constraints can be dropped and solving the cheaper LP relaxation also yields an optimal solution to the MIP.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yea... It is important to construct integral formulation. Do you think the formulation I provided is integral? thank you:D $\endgroup$ – user40780 Jul 14 '14 at 19:57

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