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
Linearization of the SMIN function?
Re: Linearization of the SMIN function?
Hi,
There are different ways to linearize smin. Actually the link you posted shows one. Translated to your example, that would result in
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
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;
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
-
- User
- Posts: 6
- Joined: 6 years ago
Re: Linearization of the SMIN function?
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.
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?
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
-Michael
Re: Linearization of the SMIN function?
Hi,
x.up is a constant that can be used inside the model. Consider the following example:
Best,
Fred
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;
Fred
-
- User
- Posts: 6
- Joined: 6 years ago
Re: Linearization of the SMIN function?
Thank you, Fred and Michael, for clarification.