# 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●4●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 ♦♦
 3 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 ♦ 3.4k●1●6●15 accept rate: 16% 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 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 (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 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. (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 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 (02 Jan '12, 17:24) Djib is x non-negative? 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 big-M for my 2 constraints in the opening post also (03 Jan '12, 04:33) Djib showing 5 of 8 show 3 more comments
 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: