Answers to: linearization of a Max function in a linear modelhttp://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model<p>Hi,</p>
<p>I want to linearize a simple max function, Let say I have a 2 dimensional variable \(X_{ts}\), and for a fixed index \(t\), I want to find the maximum value that this variable can take. </p>
<p>It can be simply done by defining/adding new variable/constraint \(Z_{t} \leq X_{ts} \; \forall t, s\) and maximizing \(Z_{t}\) beside the other constraints that already exist for the variable \(X_{ts}\).</p>
<p>However, my QUESTION is how I can find out the <em>maximum</em> value that the variable \(Z_{t}\) takes corresponds to which index \(S\). In the other words, I want to retrieve the index \(s\) of which variable \(X_{ts}\) takes the maximum value beside its maximum value which afterwards, this index will be used in other part of model.</p>
<p>Regards,<br>
Morad</p>enSat, 13 Apr 2013 12:41:04 -0400Comment by Mehrdad on Paul Rubin's answerhttp://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model#7817<p>Thank you so much Paul,</p>
<p>I have to try it to see what will be the effect on the performance of the model. Because, if I go by binary variables I HAVE to go with branch and price with my large scale model. However, with avoiding that classic column generation works. </p>
<p>Thanks again for your answer!</p>MehrdadSat, 13 Apr 2013 12:41:04 -0400http://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model#7817Answer by Paul Rubinhttp://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model/7816<p>You're talking about the <a href="http://en.wikipedia.org/wiki/Arg_max">argmax and argmin</a> functions. I don't think that you can express them linearly without using binary variables. Within some limitations, you can avoid binaries by using a quadratic constraint, as follows:\[\begin{array}{lrclr}
\textrm{max} & & Z_{t}\\
\textrm{s.t.} & Z_{t} & \le & \sum_{s}\lambda_{ts}X_{ts}\\
& \sum_{s}\lambda_{ts} & = & 1\\
& \lambda & \ge & 0\\
& S & = & \sum_{s}s\lambda_{ts}
\end{array}\]plus the other constraints on \(X\). This should work if there is a unique index \(s\) at which \(X_{ts}\) is maximal. If ties occur, I'm not positive that \(S\) will be integral (although I think it likely that it will be).</p>
<p>Personally, I'd go with binary variables rather than screwing with a quadratic constraint (especially one where the Hessian matrix is indefinite).</p>Paul RubinSat, 13 Apr 2013 11:46:48 -0400http://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model/7816Comment by Mehrdad on komar's answerhttp://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model#7814<p>Thanks for your response. Yes, it results in a min function, I did a mistake in writing the question, In fact, I linearize in that way in order to avoid introducing binary variables. Since it is of great importance for me to have a continuous formulation that is the reason behind using this technique to linearize min/max function. </p>
<p>But my problem in this method is to know exactly in which index my variable takes the maximum (minimum) value?</p>
<p>For example, in my formulation, in which index s, for the fixed \(t\), the variable \(Z_{t}\) takes the minimum value? I am wondering if there is any formulation trick to find the index \(S\) which corresponds to the minimum value of \(Z_{t}\) for a fixed \(t\) (and avoiding binary variables).</p>
<p>Thanks!<br>
Morad</p>MehrdadSat, 13 Apr 2013 03:05:59 -0400http://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model#7814Answer by komarhttp://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model/7813<p>I think defining/adding new variable/constraint \(Z_{t} \leq X_{ts} \; \forall t, s\)
and maximizing \(Z_{t}\) results in a min function.</p>
<p>Should it be the other way around?</p>
<p>Maybe your question is how we transform a max function into an MIP formulation
without involving the objective function.</p>
<p>Suppose that we want to use a following constraint:</p>
<p>\(w = \max(x_1, x_2, ..., x_n)\)</p>
<p>We can transform the above constraint into the following constraints:</p>
<p>\(x_i \leq w, \forall i \in {1...n}\)</p>
<p>\(x_i \geq w - (1 - y_i) M, \forall i \in {1...n}\)</p>
<p>\(\sum_{i=1}^n y_i \geq 1\)</p>
<p>with \(y_i\) is a binary variable.</p>komarSat, 13 Apr 2013 01:00:14 -0400http://www.or-exchange.com/questions/7809/linearization-of-a-max-function-in-a-linear-model/7813