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 % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaqbaeqabmGaaa % 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's gravatar image

accept rate: 0%

edited 21 Jul '14, 10:46


Sorry, tried to get this to look right with MathJax. I think I left the meaning clear.

(21 Jul '14, 10:39) Matthew Salt... ♦

Thank you very much :) I am also trying to :D

(21 Jul '14, 10:40) Chivalry

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.

(21 Jul '14, 18:11) Gilead ♦

What are the values of the Ji?

(02 Aug '14, 08:06) jfpuget

Interaction parameter in generalized ising model:)

(02 Aug '14, 11:22) Chivalry

Sure, but what is the range of values? Are they -1,1 or more complex?

(03 Aug '14, 15:25) jfpuget
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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

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

I don't know any references off-hand (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} - (k-1) \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

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+m-1}\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+m-1}\\ &w_{i,\ldots,i+m}\leq s_{i+m}\\ &w_{i,\ldots,i+m}\geq w_{i,\ldots,i+m-1}+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

Niels-Christian%20F%20Bagger's gravatar image

accept rate: 0%

edited 01 Aug '14, 04:26

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's gravatar image

accept rate: 8%

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) Niels-Christ...

...or: CPLEX. Or: Xpress. Or: Lindo. Or: Mosek. Or: SCIP. Or: ...

(05 Aug '14, 14:42) fbahr ♦

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's gravatar image

accept rate: 8%

edited 07 Aug '14, 05:39

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.univ-artois.fr/PB12/results/results.php?idev=67 .


answered 06 Oct '14, 16:25

VictorSMiller's gravatar image

accept rate: 0%

Fantastic! This opens a big door of my research:)

(06 Oct '14, 18:09) Chivalry
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 21 Jul '14, 10:22

Seen: 1,188 times

Last updated: 06 Oct '14, 18:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.