Is there a mathematical optimization branch that explicitly tries to optimize this (type) problem? \[\begin{array}{{20}{c}}{}&{\min }\\{}&{\mathop \sum \limits_{i = 1}^N (J * s[i] + {J_1} * s[i] * s[i + 1] + {J_2}s[i] * s[i + 1] * s[i + 2] + ... + {J_m}s[i] * s[i + 1] * ...s[i + m])}\\{}&{s[i] \in \{ 0,1\} \quad \forall i \in \{ 1,2...,N + m\} }\end{array} % MathType!MTEF!2!1!+ % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9LqJc9 % vqaqpepm0xbba9pwe9Q8fs0yqaqpepae9pg0FirpepeKkFr0xfrx % frxb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeqabmGaaa % qaaaqaaabaaaaaaaaapeGaciyBaiaacMgacaGGUbaapaqaaaqaa8qa % daGfWbqabSWdaeaapeGaamyAaiabg2da9iaaigdaa8aabaWdbiaad6 % eaa0WdaeaapeGaeyyeIuoaaOGaaiikaiaadQeacqGHxiIkcaWGZbGa % ai4waiaadMgacaGGDbGaey4kaSIaamOsa8aadaWgaaWcbaWdbiaaig % daa8aabeaak8qacqGHxiIkcaWGZbGaai4waiaadMgacaGGDbGaey4f % IOIaam4CaiaacUfacaWGPbGaey4kaSIaaGymaiaac2facqGHRaWkca % WGkbWdamaaBaaaleaapeGaaGOmaaWdaeqaaOWdbiaadohacaGGBbGa % amyAaiaac2facqGHxiIkcaWGZbGaai4waiaadMgacqGHRaWkcaaIXa % GaaiyxaiabgEHiQiaadohacaGGBbGaamyAaiabgUcaRiaaikdacaGG % DbGaey4kaSIaaiOlaiaac6cacaGGUaGaey4kaSIaamOsa8aadaWgaa % WcbaWdbiaad2gaa8aabeaak8qacaWGZbGaai4waiaadMgacaGGDbGa % ey4fIOIaam4CaiaacUfacaWGPbGaey4kaSIaaGymaiaac2facqGHxi % IkcaGGUaGaaiOlaiaac6cacaWGZbGaai4waiaadMgacqGHRaWkcaWG % TbGaaiyxaiaacMcaa8aabaaabaWdbiaadohacaGGBbGaamyAaiaac2 % facqGHiiIZcaGG7bGaaGimaiaacYcacaaIXaGaaiyFa8aacaaMf8+d % biabecGiIiaadMgacqGHiiIZcaGG7bGaaGymaiaacYcacaaIYaGaai % Olaiaac6cacaGGUaGaaiilaiaad6eacqGHRaWkcaWGTbGaaiyFaaaa % aaa!96F2! \] Currently, I only know things about Mixed integer programming (and its implementation using Gurobi)... asked 21 Jul '14, 10:22 Chivalry
showing 5 of 6
show 1 more comments

By introducing auxiliary variables, you can turn this into a MILP. Does that work for you? answered 21 Jul '14, 13:18 Paul Rubin ♦♦ It works, but the speed is still exponential to the size of the grids and rather disappointing. Say, just 64 binary would take about 10 minutes....
(21 Jul '14, 13:28)
Chivalry
It will be very appreciated if you could provide me with some reference :D
(21 Jul '14, 17:19)
Chivalry
2
I don't know any references offhand (maybe H. P. Williams's modeling book?). The way I would model a product \(s_1 * \dots * s_k\) of binary variables  and I'm not claiming this is the best way  would be to replace the product with a new variable \(w \in [0,1] \) defined by \begin{eqnarray} w & \le & s_{1} \\ w & \le & s_{2} \\ & \cdots \\ w & \le & s_{k} \\ w & \ge & s_{1} + \dots + s_{k}  (k1) \end{eqnarray}
(21 Jul '14, 20:42)
Paul Rubin ♦♦
Actually, I have been using this formulation. But the speed is very slow. a 16*8 grid takes almost forever.... Still, thank you very much:)
(22 Jul '14, 09:40)
Chivalry
It would be super great if we can find anything like an integral polytope for this....
(22 Jul '14, 10:56)
Chivalry
1
16*8 meaning N=16, m=8? If you would care to share the data for one such instance (mail to rubin #at# msu #dot# edu), I'll try an alternate formulation (when I get a chance).
(22 Jul '14, 15:29)
Paul Rubin ♦♦
showing 5 of 6
show 1 more comments

The method that Paul describes is a very common way to do it and the method I would use. However you can do a small change since the terms are very systematic. For instance suppose you have the following terms that you want to describe: \[ \begin{align} &s_i \\ &s_i\cdot s_{i+1} \\ &s_i\cdot s_{i+1}\cdot s_{i+2} \\ &\vdots\\ &s_i\cdot s_{i+1}\cdot s_{i+2}\cdot\ldots\cdot s_{i+m} \end{align} \] Then you can describe \(s_i\cdot s_{i+1}\) just as Paul describes using the variable \(w_{i,i+1}\geq0\): \[ \begin{align} &w_{i,i+1}\leq s_i\\ &w_{i,i+1}\leq s_{i+1}\\ &w_{i,i+1}\geq s_i+s_{i+1}1 \end{align} \] Then when you want to describe \(s_i\cdot s_{i+1}\cdot s_{i+2}\) you can exploit that you have the variable \(w_{i,i+1}\) as a replacement for \(s_i\cdot s_{i+1}\) meaning that \(s_i\cdot s_{i+1}\cdot s_{i+2}\) can be reformulated as \(w_{i,i+1}\cdot s_{i+2}\) and described using variable \(w_{i,\ldots,i+2}\geq0\) in the following way: \[ \begin{align} &w_{i,\ldots,i+2}\leq w_{i,i+1}\\ &w_{i,\ldots,i+2}\leq s_{i+2}\\ &w_{i,\ldots,i+2}\geq w_{i,i+1}+s_{i+2}1 \end{align} \] Then you can describe the next term in the same way and so on and so forth ending up with the expression \(s_i\cdot s_{i+1}\cdot\ldots\cdot s_{i+m}\) which can be reformulated as \(w_{i,\ldots,i+m1}\cdot s_{i+m}\) and described with variable \(w_{i,\ldots,i+m}\geq0\): \[ \begin{align} &w_{i,\ldots,i+m}\leq w_{i,\ldots,i+m1}\\ &w_{i,\ldots,i+m}\leq s_{i+m}\\ &w_{i,\ldots,i+m}\geq w_{i,\ldots,i+m1}+s_{i+m}1 \end{align} \] Since you are summing over \(i\) from 1 to \(N\) then you can probably reuse some of the variable substitutions from term to term. Now I don't know if this will be of any help to the speed but you will get a fewer number of constraints so maybe it's worth trying. answered 01 Aug '14, 04:14 NielsChrist... Thanks a lot for your answer, actually, I tried this approach but the speed up effect is hard to notice. Thanks:)
(01 Aug '14, 09:57)
Chivalry

The method from Niels Christian can be used to generate a quadratic problem. Instead of stating the constraints wi,i+1≤si wi,i+1≤si+1 wi,i+1≥si+si+1 − 1 You state wi = si * si+1 I have no idea if this would be more efficient, but it is certainly worth a try. answered 01 Aug '14, 11:32 jfpuget Thank you very much, I will try it out :)
(01 Aug '14, 11:51)
Chivalry
This is a nice observation. Some solvers (like Gurobi) have the possibility to solve quadratically constrained programs.
(05 Aug '14, 07:57)
NielsChrist...

Here is a hopefully stronger model. We will use new decision variables w_i,i+k = s_i⋅s_i+1⋅s_i+2⋅…⋅s_i+k Note that w_i,i = s_i The objective can be expressed directly with the w variables. As Niels Christian described it, you have to state these constraints w_i,j+1 = w_i,j . w_j+1,j+1 You can either linearize these constraints or keep them as is. What could strengthen the model is to also add the following constraints w_i,j = w_i,i . w_i+1,j Again you can either linearize them or keep them as is. answered 07 Aug '14, 05:33 jfpuget 
The general problem that you describe goes under the name of "Pseudo Boolean Optimization". You can read a survey article here: http://www.sciencedirect.com/science/article/pii/S0166218X01003419 . They have an annual programming competition, usually in conjuction with the SAT conference. For example, here is the page giving the results of the 2012 competition: http://www.cril.univartois.fr/PB12/results/results.php?idev=67 . answered 06 Oct '14, 16:25 VictorSMiller Fantastic! This opens a big door of my research:)
(06 Oct '14, 18:09)
Chivalry

Sorry, tried to get this to look right with MathJax. I think I left the meaning clear.
Thank you very much :) I am also trying to :D
Since s[i] are binary variables, the only viable approach that I can think of is as Paul suggests, which is to rewrite it into a MILP. However, the relaxed problem (where s[i] is continuous) can be convexified using the same log approach used in geometric programming: http://en.wikipedia.org/wiki/Geometric_programming
This will give you a bound (which may be used as a cut), but ultimately won't help you solve the discrete problem.
What are the values of the Ji?
Interaction parameter in generalized ising model:)
Sure, but what is the range of values? Are they 1,1 or more complex?