Hi,

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.

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}\).

However, my QUESTION is how I can find out the maximum 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.

Regards,
Morad

asked 12 Apr '13, 16:15

Mehrdad's gravatar image

Mehrdad
4747
accept rate: 0%

edited 13 Apr '13, 04:32

fbahr's gravatar image

fbahr ♦
4.6k716


You're talking about the argmax and argmin 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).

Personally, I'd go with binary variables rather than screwing with a quadratic constraint (especially one where the Hessian matrix is indefinite).

link

answered 13 Apr '13, 11:46

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thank you so much Paul,

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.

Thanks again for your answer!

(13 Apr '13, 12:41) Mehrdad

I think defining/adding new variable/constraint \(Z_{t} \leq X_{ts} \; \forall t, s\) and maximizing \(Z_{t}\) results in a min function.

Should it be the other way around?

Maybe your question is how we transform a max function into an MIP formulation without involving the objective function.

Suppose that we want to use a following constraint:

\(w = \max(x_1, x_2, ..., x_n)\)

We can transform the above constraint into the following constraints:

\(x_i \leq w, \forall i \in {1...n}\)

\(x_i \geq w - (1 - y_i) M, \forall i \in {1...n}\)

\(\sum_{i=1}^n y_i \geq 1\)

with \(y_i\) is a binary variable.

link

answered 13 Apr '13, 01:00

komar's gravatar image

komar
513
accept rate: 0%

edited 13 Apr '13, 04:51

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.

But my problem in this method is to know exactly in which index my variable takes the maximum (minimum) value?

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

Thanks!
Morad

(13 Apr '13, 03:05) Mehrdad
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:

×231
×127
×65

Asked: 12 Apr '13, 16:15

Seen: 7,718 times

Last updated: 13 Apr '13, 13:24

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