How to transform a maximizing objective function which contains a max operator to a standard LP form

Question

My Optimization objective function looks like this:

$\max\quad(c_1 x_1 + c_2 \max\{x_2, x_3, x_4\})$

all variables, $x_i$ are binary variables. There are also some linear constraints such as $a_ix_1 + a_2 x_2 + a_3 x_3 < 3$. I am asking is there any method which could help to transform this objective function to a standard form (which means there is no max-max).

I know there is a method which uses big-M coefficient. I need to transform the objective function to this one:

$\max\quad(c_1 x_1 + c_2x_5)$

while add 4 other constraints:

$$ x_5 \leq x_2 + x_6M\\ x_5 \leq x_3 + x_7M\\ x_5 \leq x_4 + x_8M\\ x_6 + x_7 + x_8 = 2 $$

$M$ is a big enough coefficient and $x_6, x_7, x_8$ are binary. I was wondering whether my transformation is correct. Since $x_i$ are all binary, is there any simpler method? If any one of $x_2, x_3, x_4$ is 1, the objective function could turn to $c_1x_1 + c_2$

Answer 1

Do it like this: introduce a new binary decision variable $z \in \{0,1\}$ and write the objective as: $$ \min -c_1x_1 - c_2z$$ subject to: $$ z\ge x_2$$ $$ z \ge x_3 $$ $$ z \ge x_4 $$

plus all remaining original constraints.

In short, we are simply modeling $ z = \max\{x_2,x_3,x_4\}$ and changing the problem type to min-max.