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's gravatar image

Djib
23114
accept rate: 0%

retagged 12 Oct '12, 05:50

yeesian's gravatar image

yeesian
846210


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.

link

answered 04 Jan '12, 08:48

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 27 Aug '13, 13:49

fbahr's gravatar image

fbahr ♦
4.6k716

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?

link

answered 02 Jan '12, 07:32

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
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 ♦♦
(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

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<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.

link

answered 12 Aug '15, 06:20

RuneR's gravatar image

RuneR
192
accept rate: 0%

edited 13 Aug '15, 15:07

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_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

link

answered 02 Jan '12, 07:16

Pradeep's gravatar image

Pradeep
0
accept rate: 0%

@pradeep: note that the question was: "... to linear constraints..."

(02 Jan '12, 07:34) Marco Luebbecke ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×79
×65

Asked: 02 Jan '12, 06:45

Seen: 20,436 times

Last updated: 13 Aug '15, 15:07

OR-Exchange! Your site for questions, answers, and announcements about operations research.