Dear all, the last few days i've been struggling with two nonlinear constraints i want to transform to linear ones: y <= max (x1,x2) and y >= min (x1,x2) I've tried multiple alternatives, using the BigM 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\\ \textrm{with} & \delta & & \textrm{binary} \end{eqnarray} \] 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. answered 04 Jan '12, 08:48 Paul Rubin ♦♦ fbahr ♦ 1
And now that I'm fully awake, we can drop the first two constraints (valid but redundant) and just use the last two.
(04 Jan '12, 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?
(04 Jan '12, 18:12)
Djib
If (yle x_1) and (x_1) isn't the max, then (yle x_1 lt x_2).
(04 Jan '12, 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?
(05 Jan '12, 03:42)
Djib
1
No, constraints 3 and 4 say that (yle x_1) OR (yle x_2) (inclusive or), which implies that (ylemax(x_1,x_2)). You would need AND for (ylemin(x_1,x_2)).
(05 Jan '12, 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? answered 02 Jan '12, 07:32 Marco Luebbecke ♦ 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.
(02 Jan '12, 08:25)
Thiago Serra
Thanks already for your answers. Well, the only purpose is to transform it with bigM 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
(02 Jan '12, 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).
(02 Jan '12, 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 ORExchange would be more useful if we were more liberal with the use of downvotes, and if people did not see a downvote as a slap in the face, just as an upvote is not a sign of true love.
(02 Jan '12, 16:35)
Michael Trick ♦♦
@mike trick: +1
(02 Jan '12, 16:48)
Marco Luebbecke ♦
Maybe this can give you some extra insights in my problem. The following nonlinear constraint I was able to solve with bigM: If(y=1) then x>=10 else if (y=0) then x<=5 becomes (with x=continuous and y=binary) x>= 10y  M(1y) and x<= 5(1y) + My
(02 Jan '12, 17:24)
Djib
is x nonnegative? then the first constraint is x>= 10y. this formulation looks ok to me, what is wrong with it?
(02 Jan '12, 17:38)
Marco Luebbecke ♦
Nothing wrong with this one, I was just providing an example to show that it should be possible with bigM for my 2 constraints in the opening post also
(03 Jan '12, 04:33)
Djib
showing 5 of 8
show 3 more comments

THE FOLLOWING IS WRONG  IT CANNOT BE DONE WITH LINEAR CONSTRAINTS AS THE FUNCTION \(\max(x_1,x_2)\) IS NOT CONVEX AND \(\min(x_1,x_2)\) IS NOT CONCAVE. \( y \le \max(x_1,x_2)\) is equivalent to: \( z \le x_1 \) \(z\le x_2\) \(y \le x_1+x_2z\) with \(z\in\mathbb{R}.\) Proof: There exists \(z\) such that \(y\le\max(x_1,x_2)\), with \(z=\min(x_1,x_2)\). So adding the three above inequalities ensures \(y\) such that \(y\le\max(x_1,x_2)\) are feasible with some \(z\) and \(y\) such that \(y>\max(x_1,x_2)\) are not feasible for any \(z\) as \(y \le x_1+x_2z \le x_1+x_2\min(x_1,x_2)=\max(x_1,x_2)\). \( y \ge \min(x_1,x_2)\) is equivalent to: \(w\ge x_1\) \(w\ge x_2\) \(y\ge w(x_1+x_2)\) with \(w\in\mathbb{R}. \) Proof: There exists \(w\) such that \(y\ge \min(x_1,x_2)\) with \(w=\max(x_1,x_2)\). So adding the three above inequalities ensures that \(y\) such that \(y\ge \min(x_1,x_2)\) are feasible with some \(w\) and such that \(y<min(x_1,x_2)\) are not feasible for any \(w\) as \(y\ge w(x_1+x_2) \ge \max(x_1,x_2)(x_1+x_2)=\min(x_1,x_2)\). These inequalities keep linearity and avoid including binary variables. answered 12 Aug '15, 06:20 RuneR You said \(y > \max(x_1, x_2)\) is not feasible for any \(z\), but \(z = 0\) and \(y = x_1 + x_2 > \max(x_1, x_2)\) satisfies the first three inequalities.
(12 Aug '15, 10:16)
Paul Rubin ♦♦
But z=0 and y=x_1+x_2 is only feasible if x_1<=0 and x_2<=0, but if x_1<=0 and x_2<=0 then we don't have: x_1+x_2>max(x_1,x_2)
(12 Aug '15, 10:20)
RuneR
That doesn't make sense. If x1=5 and x2=7, then if z=0, y=12 satisfies all the constraints. There is nothing here about negative values.
(13 Aug '15, 06:34)
Mike Trick ♦♦
Is the latter case, the third condition is correct? It seems to me that there is the following relationship \(y\geq w (x_1+x_2)\geq max(x_1,x_2) (x_1+x_2)=min(x_1,x_2) \). And then \(y\geq min(x_1,x_2)\) is not the same as \(y\geq min(x_1,x_2)\). Similarly, in the first case, if the \(z\leq min(x_1,x_2)\), it is not true that\(x_1+x_2z\leq x_1+x_2min(x_1,x_2)\). That problem is not so difficult, because there are only three possibilities:\[ x_1\leq x_2 \vee x_1\geq x_2 \vee x_1=x_2\] Then:\[x_1\leq y\leq x_2 \, \vee x_2\leq y\leq x_1 \, \vee x_1=x_2=y\]
(13 Aug '15, 14:07)
Slavko
2
It was wrong. I made an error with a sign. It can't be done with linear constraints only.
(13 Aug '15, 15:06)
RuneR

max(x1,x2) = (x1x2)^(+) + x2 min(x1,x2) = x1  (x1x2)^(+) we define (x1x2)^(+) = x1x2 if x1>=x2 = 0 otherwise answered 02 Jan '12, 07:16 Pradeep @pradeep: note that the question was: "... to linear constraints..."
(02 Jan '12, 07:34)
Marco Luebbecke ♦
