# Transform non-linear to linear constraints manually

 2 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 asked 02 Jan '12, 06:45 Djib 23●1●1●4 accept rate: 0% yeesian 846●2●10

 6 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 ♦♦ 14.6k●5●13 accept rate: 19% fbahr ♦ 4.6k●7●16 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 ♦♦
 0 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_2-z$$ 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_2-z \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 \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_2-z\leq x_1+x_2-min(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
 -4 max(x1,x2) = (x1-x2)^(+) + x2 min(x1,x2) = x1 - (x1-x2)^(+) we define (x1-x2)^(+) = x1-x2 if x1>=x2 = 0 otherwise answered 02 Jan '12, 07:16 Pradeep 0 accept rate: 0% @pradeep: note that the question was: "... to linear constraints..." (02 Jan '12, 07:34) Marco Luebbecke ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Seen: 20,643 times

Last updated: 13 Aug '15, 15:07