How to avoid quadratic expression?

[PWG]

Hi All,

I've encountered a problem in terms of avoiding using quadratic expression. Suppose I have three variables x, y, z. y is a Boolean variable; z is an integer with values ranging in [0,100]. If y = 0, we have x = 0; if y = 1, we have x = z. Intuitively we can use this expression x = y*z, but it is quadratic. I wonder is there any way I can avoid this and come up with a linear expression? Thanks!

[Johan Löfberg]

Exactly as you've done it.

Either manually through big-M

intvar x
intvar z
binvar y
Model = [0 <= z <= 100, 0<= x <= 100*y,0 <= z-x <= 100*(1-y)
 

or automatically using implies (which derives the big-M model

Model = [0 <= z <= 100,implies(y,x==0), implies(1-y,x==z)];

or through the general binmodel command for polynomial expressions

Model = [0 <= z <= 100];
Model2 = binmodel(z*y,Model);

Model = [Model,Model2];

[PWG]

Wow, cool! That solves the problem! So if I have two variables x, y. y is an integer taking values in [0,100]; x is a Boolean variable. And we have x = 1 if y >0 and x = 0 if y = 0. How to describe the relationship of x and y? Suppose I am trying to minimize an objective function f, and from the expression of f we know that x and y are the smaller the better in order to minimize.

[Johan Löfberg]

[implies(y>=0,x==1),implies(y==0,x==0), lowerbound <= y <= upperbound]

Bounds needed for big-M
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Implies

[Johan Löfberg]

since y is integer, I would use the numerically less sensitive model implies(y>=1/2,x==1)

[PWG]

Hi, I prefer doing it manually, meaning without using function implies. I tried using this: x>= y/100. From this expression we can see: if y >0, x=1; if y=0, x=0 or 1. But since x is the smaller the better, we can have "if y=0, x=0". I wonder if there is any more elegant way of expressing the relationship of x and y?

[Johan Löfberg]

If y goes positive, this one forces x to be true

y <= 100*x

If y is zero, x must be zero (I assume y is a non-negative variable)

-y<=x<=y

[PWG]

Thank you Johan! Problems solved!