问题描述
我正在尝试使用整数编程来优化目标函数，我必须在函数中使用Max运算符，我想知道有什么方法可以解决这个问题吗?
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?
实际上，我的问题类似于在整数线性程序中使用min/max ，但在某些方面有所不同:
Actually my question is similar to Using min/max within an Integer Linear Program but is different in some aspects:
- 所有变量都是二进制的.
- 请注意，
x4和x5出现在两个位置. - 一个可能的解决方案是使用辅助变量，例如，但是在我的示例中使用这种解决方案时，我感到困惑.
- All variables are binary.
- Note that
x4andx5are 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:
最小化 (c1 * x1) + (c2 * x2) + (c3 * x3) + Max(c4 * x4, c5 * x5) + (c6 * x4) + (c7 * x5)
要遵守
一些平等和不平等约束
推荐答案
在链接的问题中使用该方法.表达式
Use the approach in the question you linked. The expression
Max(c4 * x4, c5 * x5)
如果您添加以下附加约束，则可以用变量x6代替
:
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)
必须遵守:
some equality and inequality constraints
和新要求:
x6 >= c4 * x4
x6 >= c5 * x5
之所以可行，是因为Max(c4 * x4, c5 * x5)将采用值c4 * x4或c5 * x5.引入的变量x6将始终大于或等于这两个表达式，因此将始终大于或等于总的max-expression.如果适当地将其最小化，则x6将在max-expression的值处达到最低点.因此，当最小化时，这两种形式是等效的.
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.
这篇关于在整数编程中使用最小/最大运算符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！