Tuesday, July 22, 2008

Modeling question

>I need to change the following non linear constraint to a linear one .
>the constraints are:
>
>for all k = 0 ,1, 2,3 ,4,...... 10
>
>k+1 = sum over j ( a[k][j] * d[j] )
>
>j = 1,2,3,4
>
>for all k, j a[k][j] is an integer <= 2 and d[j] is an integer <= 60. >
>both a[k][j] and d[j] are variables , making it a non linear
>constraint. Is there a method i can change it to a linear expression.
>Cplex gives a error with this constraint.


These question can only be answered more definitely by looking at the complete model, but let me give it a shot anyway.

The a(k,j) variables can only assume the values 0,1,2. So we can write this as a sum of 2 binary variables (and relax a to be continuous):

0 <= a(k,j) <= 2 continuous
b1(k,j), b2(k,j) binary
a(k,j) = b1(k,j)+2*b2(k,j);

Now we can express z(k,j) = a(k,j)*d(j) as

M1=20
z1(k,j) ≤ M1 · b1(k,j)
z1(k,j) ≤ d(j)
z1(k,j) ≥ d(j) − M1 · (1 − b1(k,j))
M2=40
z2(k,j) ≤ M2 · b2(k,j)
z2(k,j) ≤ 2*d(j)
z2(k,j) ≥ 2*d(j) − M2 · (1 − b2(k,j))
k + 1 = sum(j, z1(k,j)+z2(k,j));

See also: http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/multiplication-of-continuous-and-binary.html.