Page 1 of 1
Linearization of the SMIN function?
Posted: Wed May 23, 2018 8:55 am
by GamsUser80
Dear All,
Is there any way to convert the below equation to be linearized:
Constraint1(t).. Y(t) =e= Smin(i, sum(j, x(i,j,t)) ;
In the simple words, I want Y(t) to get the minimum value of that summation for each i.
I have found this topic from archive however it is a bit confusing.
viewtopic.php?f=13&t=9754&p=22238&hilit ... ive#p22238
Regards,
Sean
Re: Linearization of the SMIN function?
Posted: Wed May 23, 2018 4:52 pm
by Fred
Hi,
There are different ways to linearize smin. Actually the link you posted shows one. Translated to your example, that would result in
Code: Select all
[...]
positive variable slack(t,i);
binary variable indslack(t,i);
[...]
Constraint1(t,i).. Y(t) =l= sum(j, x(i,j,t));
Constraint2(t,i).. Y(t) =e= sum(j, x(i,j,t)) - slack(t,i);
Constraint3(t,i).. slack(t,i) =l= indslack(t,i)*smax(j, x.up(i,j,t));
Constraint4(t).. sum(i, indslack(t,i)) =l= card(j) - 1;
As Michael mentioned in his linked post, Constraint1 becomes obselete in this reformulation because it is enforced by constraint2 and the positive slack.
Constraint 4 makes sure that (for every t) there is at least one i with indslack(t,i)=0. In consequence, constraint3 ensures that slack(t,i) is zero to for the same i.
If the objective function wants the variables Y(t) to be as big as possible and no other constraints will keep Y(t) from achieving equality in Constraint1, that particular constraint should actually be sufficient.
I hope this helps!
Best,
Fred
Re: Linearization of the SMIN function?
Posted: Thu May 24, 2018 1:44 am
by GamsUser80
Hi Fred,
Thanks for your response. I still can not run the model with MIP because of the Smax part in constraint 3 (error 66). when I deactivated this constraint the model runs but gives the wrong result though. Since x(i,j,t) is a variable as well, are we allowed to use x.up inside the model as part of constraint?
Thanks.
Re: Linearization of the SMIN function?
Posted: Thu May 24, 2018 8:20 am
by bussieck
If you read Fred's code carefully, he is using x.up in the smax operator. The upper bound of the variable (not the variable itself). x.up can be replaced by any number that is to be guaranteed an upper bound on the x variable. We have seen models where users just use 1e9 or other crazy numbers. While this is mathematically (often) true is it numerically disastrous, so select the smallest upper bound of x (which is usually x.up or some implied upper bound) inside smax. Try to understand what these equations do for you then you will understand what you actually have to use for the different terms.
-Michael
Re: Linearization of the SMIN function?
Posted: Thu May 24, 2018 8:28 am
by Fred
Hi,
x.up is a constant that can be used inside the model. Consider the following example:
Code: Select all
set t /t1*t5/
i /i1*i3/
j /j1*j2/
;
variable x(i,j,t)
Y(t)
z;
positive variable slack(t,i);
binary variable indslack(t,i);
equation Constraint1(t,i), Constraint2(t,i), Constraint3(t,i), Constraint4(t), obj;
Constraint1(t,i).. Y(t) =l= sum(j, x(i,j,t));
Constraint2(t,i).. Y(t) =e= sum(j, x(i,j,t)) - slack(t,i);
Constraint3(t,i).. slack(t,i) =l= indslack(t,i)*smax(j, x.up(i,j,t));
Constraint4(t).. sum(i, indslack(t,i)) =l= card(j) - 1;
obj.. z =e= sum(t, Y(t));
model m /all/;
x.lo(i,j,t) = uniform(1,5);
x.up(i,j,t) = uniform(5,10);
solve m min z use mip;
parameter rep(t,*);
rep(t,'smin') = Smin(i, sum(j, x.l(i,j,t)));
rep(t,'Y_t') = Y.l(t);
display rep;
Best,
Fred
Re: Linearization of the SMIN function?
Posted: Thu May 24, 2018 10:24 am
by GamsUser80
Thank you, Fred and Michael, for clarification.