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$


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

  • $\begingroup$ 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\}$ $\endgroup$
    – sensenli
    Commented Jul 20, 2014 at 20:20
  • $\begingroup$ 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$. $\endgroup$
    – baudolino
    Commented Jul 20, 2014 at 20:30
  • $\begingroup$ Oh,yeah. That's one way to do that. Thanks a lot $\endgroup$
    – sensenli
    Commented Jul 20, 2014 at 20:32
  • $\begingroup$ 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 $\endgroup$
    – sensenli
    Commented Jul 20, 2014 at 20:40
  • $\begingroup$ It should not because the constraints $z \ge ...$ model the max piece, and that remains unchanged. You're only changing the cost coefficients. $\endgroup$
    – baudolino
    Commented Jul 20, 2014 at 20:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .