I am trying to linearize the following inequality:

X>=Min (Y,Z)

where X, Y, and Z are continuous variables and I am trying to minimize X in the objective function. I do not want to use a binary variable if possible.

I really appreciate your help.



asked 03 Sep '16, 19:13

_Jonah_'s gravatar image

accept rate: 0%

X >= min(Y.Z) is equivalent to Y - X <= 0 non-exclusive or Z - X <= 0

Introduce a binary variable B. Let M1 be an upper bound on Y - X, and M2 be an upper bound on Z - X.

Use the constraints:

Y - X <= M1 * B

Z - X <= M2 * (1-B)

I don't believe X >= min(Y,Z) can be "linearized" in isolation without use of an integer variable (or other non-convex restriction) of some sort. The reason is that min(Y,Z) is a concave function of Y and Z. Therefore X >= min(Y,Z) is a non-convex constraint. Suppose it could be lnearized without use of integer variables (note: integer variables are non-convex constraints). The resulting system of linear constraints would be convex, i.e. specify a convex set, which is inconsistent with the original constraint min(Y,Z) being non-convex. So my assertion is proved by contradiction.

Note that I analyzed the constraint X >= min(Y,Z) in isolation. It is possible that if there are other constraints in the problem, this situation might change. For instance, let's say as an extreme case, that there is also a constraint X >= max(Y,Z). Then the constraint X >= min(Y,Z) can be "linearized" by eliminating it as a redindant constraint.


answered 04 Sep '16, 09:11

Mark%20L%20Stone's gravatar image

Mark L Stone
accept rate: 15%

edited 04 Sep '16, 09:13

Dear Mark,

Thank you so much for your answer. I believe these two constraints suffice.

As you have mentioned I also constraints such as X<=A and X<=B which provides upper bounds on variable X and forces the X variable to receive at most the minimum value. My problem was to prevent the model to assign a value less than the minimum of A and B.

By the way, I also found a website where the author claims that min functions can be linearized without using binary variables. You can reach the website from here. Do you think that the proposed method on the website is legitimate?

Thanks for your answer again.



answered 05 Sep '16, 00:27

_Jonah_'s gravatar image

accept rate: 0%

Hopefully someone else will chime in, but the solution proposed in the link ends with the statement "Remember to penalize S^- and S^+ such that only one of them will be different from zero in any solution." How is this penalization going to be done without adding a non-convex nonlinear "thing" somewhere in the problem formulation? So I think the proposed formulation merely shifts the non-convex nonlinearity to elsewhere.

(05 Sep '16, 09:16) Mark L Stone

Dear Mark,

Thank you so much for your answer. Is this a conventional linearization, how can I site this method?

(05 Sep '16, 15:49) _Jonah_

The approach I used is Big M, which introduces a binary variable. In reality, you should make M just big enough, not too big, otherwise you could introduce numerical difficulties to the solver. You'll also notice that I used separate "M's" for each constraint, which contributes toward allowing them to be just big enough.

(05 Sep '16, 16:48) Mark L Stone

Hello Mark,

Thank you for your explanation.

I wanted to ask how should we come up with the Value for M's?



answered 16 Oct '16, 15:40

ARS's gravatar image

accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 03 Sep '16, 19:13

Seen: 2,366 times

Last updated: 16 Oct '16, 15:40

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