# Polynomial binary programming

 1 1 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 229●2●18 accept rate: 0% 1 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 1 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 ♦ 1 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

 4 By introducing auxiliary variables, you can turn this into a MILP. Does that work for you? answered 21 Jul '14, 13:18 Paul Rubin ♦♦ 14.6k●4●12 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 2 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 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
 4 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-Christ... 71●4 accept rate: 0% 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
 2 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 2.5k●3●10 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... 1 ...or: CPLEX. Or: Xpress. Or: Lindo. Or: Mosek. Or: SCIP. Or: ... (05 Aug '14, 14:42) fbahr ♦
 1 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 2.5k●3●10 accept rate: 8%
 1 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 343●2●15 accept rate: 0% Fantastic! This opens a big door of my research:) (06 Oct '14, 18:09) Chivalry
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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

Tags:

×190
×101