I wonder how I can linearize the following expression:

$$z = \sum_{i=1}^{n} \max_{j=1,...,n} (y_{ij})$$

Thanks in advance.

asked 11 Feb '16, 07:20

monash's gravatar image

accept rate: 0%

edited 18 Feb '16, 05:16

Did you perhaps mean max instead of argmax?

(11 Feb '16, 10:35) Rob Pratt

@RobPratt: Yes actually, and I revised it. I represented it by the mathematical optimization notation.

(11 Feb '16, 11:14) monash

Hint: introduce a new variable \(x_j\) to represent the summand, linearize that in the usual way, and take \(z = \sum_{j=1}^n x_j\).


answered 11 Feb '16, 13:33

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

It depends on how variable z relates to the objective function.

(11 Feb '16, 15:30) monash

... and how does z relate to the objective? Is the solver trying to minimize z (in which case inequalities alone should work), or not (in which case you'll need a gaggle of binary variables)?

(11 Feb '16, 15:43) Paul Rubin ♦♦

The solver is trying to minimize -Z .

(11 Feb '16, 15:53) monash

I found the best possible strategy is to impose these constraints sets:

$$x_i \geq \frac 1n \sum_{j=1}^{n} y_{ij}, \quad \forall i = 1,...,n$$

$$x_i \leq \sum_{j=1}^{n} y_{ij}, \quad \forall i = 1,...,n$$

and then:

$$z = \sum_{i=1}^{n} x_i$$


answered 12 Feb '16, 13:48

monash's gravatar image

accept rate: 0%

edited 18 Feb '16, 05:12

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: 11 Feb '16, 07:20

Seen: 3,250 times

Last updated: 18 Feb '16, 05:16

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