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

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

$$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$

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$$
In short, we are simply modeling $z = \max\{x_2,x_3,x_4\}$ and changing the problem type to min-max.
• I have considered your idea before. it is not appropriate in this setting because it will only give correct answer with objective function which looks like $\min c_1x_1 + c_2 \max\{x_3, x_4, x5\}$ Commented Jul 20, 2014 at 20:20
• You can convert from $\max$ to $\min$ by multiplying by $-1$, so I don't see what the problem is. Change your goal to say $\min -c_1x_1 - c_2z$. Commented Jul 20, 2014 at 20:30
• I am afraid If i transform like that. It turns to $\min−c_1x_1−c_2\min\{x_3, x_4, x_5\}$. Still, it is not the max-min or min-max form Commented Jul 20, 2014 at 20:40
• It should not because the constraints $z \ge ...$ model the max piece, and that remains unchanged. You're only changing the cost coefficients. Commented Jul 20, 2014 at 20:48