0
$\begingroup$

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$

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\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 Jul 20 '14 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 Jul 20 '14 at 20:30
  • $\begingroup$ Oh,yeah. That's one way to do that. Thanks a lot $\endgroup$ – sensenli Jul 20 '14 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 Jul 20 '14 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 Jul 20 '14 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.