# Linearization of Min Function

 0 Hello, 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. Thanks, Jonah asked 03 Sep '16, 19:13 _Jonah_ 11●2 accept rate: 0%

 1 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 L Stone 447●3●10 accept rate: 15%
 0 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. Jonah answered 05 Sep '16, 00:27 _Jonah_ 11●2 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
 0 Hello Mark, Thank you for your explanation. I wanted to ask how should we come up with the Value for M's? Azhar answered 16 Oct '16, 15:40 ARS 11●1 accept rate: 0%
 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: