mathematical-optimization - 在整数规划中使用最小/最大运算符

Question

我正在尝试使用整数规划优化目标函数，我必须在我的函数中使用 Max 运算符，我想知道有什么办法可以解决这个问题吗？

实际上我的问题类似于Using min/max within an Integer Linear Program但在某些方面有所不同:

• 所有变量都是二进制的。
• 请注意，x4 和 x5 出现在两个地方。
• 一种可能的解决方案是使用辅助变量，例如 similar question 的答案。 ，但在我的示例中使用此解决方案时，我感到很困惑。

示例:

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

受制于
一些平等和不平等约束

Answer 1

使用您链接的问题中的方法。表达式

Max(c4 * x4, c5 * x5)

可以替换为变量 x6，前提是您添加以下附加约束:

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

所以你的总集变成了:

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 的值处触底。所以当最小化时，这两种形式是等价的。