Using min/max operator in integer programming

Question

I am trying to optimize an objective function using integer programming, I have to use Max operator in my function, I want to know is there any way to deal with that?

Actually my question is similar to Using min/max within an Integer Linear Program but is different in some aspects:

All variables are binary.
Note that x4 and x5 are presented in two place.
One possible solution is using auxiliary variables like the answer of similar question, but I am confused when using this solution for my example.

Example:

Minimize (c1 * x1) + (c2 * x2) + (c3 * x3) + Max(c4 * x4, c5 * x5) + (c6 * x4) + (c7 * x5)

subject to
some equality and inequality constraints

It's refreshing when someone posts in the beginning why it differs from similar questions. — Dennis Meng
– Dennis Meng, Commented Dec 29, 2013 at 23:09
@Dennis Meng, sorry, I can't understand what you mean, my question isn't clear enough? — oMiD
– oMiD, Commented Dec 29, 2013 at 23:15
Not at all. I was remarking on how you mentioned at the beginning why this isn't exactly like the other question. It's a good thing. :) — Dennis Meng
– Dennis Meng, Commented Dec 29, 2013 at 23:17
It seems to me that you can use the technique in the other answer which you linked, are you running into problems? — Alexander Torstling
– Alexander Torstling, Commented Dec 29, 2013 at 23:24

Alexander Torstling · Accepted Answer · 2013-12-29 23:36:29Z

7

Use the approach in the question you linked. The expression

Max(c4 * x4, c5 * x5)

can be replaced by a variable x6, provided that you add the following additional constraints:

x6 >= c4 * x4
x6 >= c5 * x5

So you total set becomes:

Minimize (c1 * x1) + (c2 * x2) + (c3 * x3) + x6 + (c6 * x4) + (c7 * x5)

subject to:

some equality and inequality constraints

and the new requirements:

x6 >= c4 * x4
x6 >= c5 * x5

This works since Max(c4 * x4, c5 * x5) will either take the value c4 * x4 or c5 * x5. The introduced variable x6 will always be larger or equal to both of these expressions, and so will always be larger or equal to the total max-expression. When properly minimized, x6 will bottom out at the value of the max-expression. So when minimized, the two forms are equivalent.

answered Dec 29, 2013 at 23:36

Alexander Torstling

19k7 gold badges64 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

oMiD Over a year ago

thanks for your very clear explanation, I totally get that :)

Collectives™ on Stack Overflow

Using min/max operator in integer programming

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related