Linearization of the SMIN function?

Problems with modeling
Post Reply
GamsUser80
User
User
Posts: 6
Joined: 6 years ago

Linearization of the SMIN function?

Post 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
Fred
Posts: 372
Joined: 7 years ago

Re: Linearization of the SMIN function?

Post 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
GamsUser80
User
User
Posts: 6
Joined: 6 years ago

Re: Linearization of the SMIN function?

Post 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.
User avatar
bussieck
Moderator
Moderator
Posts: 1033
Joined: 7 years ago

Re: Linearization of the SMIN function?

Post 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
Fred
Posts: 372
Joined: 7 years ago

Re: Linearization of the SMIN function?

Post 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
GamsUser80
User
User
Posts: 6
Joined: 6 years ago

Re: Linearization of the SMIN function?

Post by GamsUser80 »

Thank you, Fred and Michael, for clarification.
Post Reply