问题描述
我正在尝试使用整数编程来优化目标函数,我必须在函数中使用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
x4
andx5
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:
最小化 (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.
这篇关于在整数编程中使用最小/最大运算符的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!