Linearization of the SMIN function?

GAMS
1

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.
https://newforum.gams.com/t/alternative-for-smin-function-in-minlp/1713/5

Regards,
Sean

2

Hi,

There are different ways to linearize smin. Actually the link you posted shows one. Translated to your example, that would result in

[...]
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

3

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.

4

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

5

Hi,

x.up is a constant that can be used inside the model. Consider the following example:

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

6

Thank you, Fred and Michael, for clarification.