equivalent of square binary variable summation

[Julio López]

Dear all

 

I need solve

 

[sum(2^m xm)]^2*yk where x is a binary variable, y is a continue variable and m and k are subindexes. My problema is how I find an equivalent for square of binary variable summation.

 

Regards 

 

Julio

[Robert Fourer]

You can always multiply out the square of the sum of binary variables, giving a sum of simple quadratic terms of two kinds:

-- constant times x[m], which is trivially linearized by observing that x[m]^2 = x[m] for any binary variable x[m]

-- constant times x[m] * x[n], which can be linearized in a well-known way by substituting a new binary variable z[m,n] for x[m] * x[n] and then adding a few simple constraints that force z[m,n] to equal x[m] * x[n]

After all of these transformations are made, the square becomes a linear expression in binary variables. Then your overall expression becomes a sum of terms, each consisting of a binary variable times a continuous variable, for which there is also a well-known linearization.

This does not seem like a very promising approach, however, as it relies heavily on linearization tricks and adds a large number of variables and constraints to the problem. It would be worth trying to re-think the formulation entirely, based on your knowledge of the actual problem. to try to avoid an awkward expression like (sum {i in 2..m} x[i])^2 * y[k]. Alternatively you could try a nonlinear mixed-integer solver like KNITRO, Bonmin, or Couenne.

Bob Fourer
am...@googlegroups.com

=======