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$
Best Answer
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.