|
Dear all, the last few days i've been struggling with two non-linear constraints i want to transform to linear ones: y <= max (x1,x2) and y >= min (x1,x2) I've tried multiple alternatives, using the Big-M method and dummy variables but I don't seem to find the right solution. Could anyone help me further with this? Best regards, Djib |
|
Assuming all variables are bounded, doesn't \begin{eqnarray*} x_{1} & \le & x_{2}+M\delta\\ x_{2} & \le & x_{1}+M(1-\delta)\\ y & \le & x_{1}+M(1-\delta)\\ y & \le & x_{2}+M\delta \end{eqnarray*} with \(\delta\) binary take care of \(y\le \max(x_1,x_2)\)? Assuming yes (I'm still on my first cup of coffee), the min version should follow easily. And now that I'm fully awake, we can drop the first two constraints (valid but redundant) and just use the last two.
(Jan 04 at 13:32)
Paul Rubin ♦
Thanks a lot, exactly what I was looking for! Though, shouldn't we keep the first 2 constraints? For example, with δ=1 (similar for δ=0) you get: x2≤x1 and y<=x1 which guarantees that y≤max(x1,x2) since we know here that x1 is maximum. But when you drop the first 2 constraints, for δ=1 the only relevant constraint is then y≤x1 which does not guarantee that y≤max(x1,x2)since we don't know that x1 is maximum?
(Jan 04 at 18:12)
Djib
If \(y\le x_1\) and \(x_1\) isn't the max, then \(y\le x_1 \lt x_2\).
(Jan 04 at 21:17)
Paul Rubin ♦
Indeed, so dropping the first 2 constraints represents y ≤ min(x1,x2) instead of y ≤ max(x1,x2), if I understand correctly?
(Jan 05 at 03:42)
Djib
1
No, constraints 3 and 4 say that \(y\le x_1\) OR \(y\le x_2\) (inclusive or), which implies that \(y\le\max(x_1,x_2)\). You would need AND for \(y\le\min(x_1,x_2)\).
(Jan 05 at 14:30)
Paul Rubin ♦
|
|
with linear constraints you can probably only reformulate that as "soft constraints". the classic for y <= max (x1,x2): x1 <= z x2 <= z y <= z and z must be penalized in the objective function. y >= min (x1,x2) is similar: z >= x1 z >= x2 y >= z Note that this does not guarantee that y is actually smaller than the max (resp. larger than the min). Also note that -- as usual with large penalties in the objective function -- you may run into numerical troubles. To avoid all this, maybe you can post the purpose of your constraints and we can find an entirely different way of modeling it? Sometimes the penalty is not necessary. It might be the case that the objective function of your problem induces that optimal solutions possess certain properties. However, as Marco said, it is hard to see that without further information.
(Jan 02 at 08:25)
Thiago Serra
Thanks already for your answers. Well, the only purpose is to transform it with big-M and/or dummy variable to linear without any further ado for now. Should undoubtedly be possible for those 2 constraints I was told but still don't manage to solve it
(Jan 02 at 11:14)
Djib
@Djib Thankfully, we have CIP techniques for this ...oh wait, that's where you were coming from. - Actually, I'm disappointed that "pure" ILP [I've to guess here, \(y, x_{1,2} \in N_0\)?] doesn't provide a more elegant solution than soft constraints (and, btw, I also think that "you" (@all) have been a bit harsh on @Pradeep's answer ...I posted way more stupid answers than his in the past and [mis]earned upvotes).
(Jan 02 at 14:43)
fbahr ♦
1
A "-" serves, in my mind, mainly to the readers: it says, this is not the answer to the question. I think OR-Exchange would be more useful if we were more liberal with the use of down-votes, and if people did not see a down-vote as a slap in the face, just as an up-vote is not a sign of true love.
(Jan 02 at 16:35)
Michael Trick ♦♦
@mike trick: +1
(Jan 02 at 16:48)
Marco Luebbecke
|
|
Maybe this can give you some extra insights in my problem. The following non-linear constraint I was able to solve with big-M: If(y=1) then x>=10 else if (y=0) then x<=5 becomes (with x=continuous and y=binary) x>= 10y - M(1-y) and x<= 5(1-y) + My is x non-negative? then the first constraint is x>= 10y. this formulation looks ok to me, what is wrong with it?
(Jan 02 at 17:38)
Marco Luebbecke
Nothing wrong with this one, I was just providing an example to show that it should be possible with big-M for my 2 constraints in the opening post also
(Jan 03 at 04:33)
Djib
|
|
max(x1,x2) = (x1-x2)^(+) + x2 min(x1,x2) = x1 - (x1-x2)^(+) we define (x1-x2)^(+) = x1-x2 if x1>=x2 = 0 otherwise @pradeep: note that the question was: "... to linear constraints..."
(Jan 02 at 07:34)
Marco Luebbecke
|
It seems to me that the constraint-programming tag is not suited to this question. I suggest removing it.