在整数规划中使用最小值/最大值运算符

Question

我正在尝试使用整数规划优化目标函数，我必须在我的函数中使用Max运算符，我想知道是否有任何处理方法？

实际上，我的问题类似于在整数线性规划中使用min/max，但在某些方面有所不同：

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

示例： 最小化(c1 * x1) + (c2 * x2) + (c3 * x3) + Max(c4 * x4, c5 * x5) + (c6 * x4) + (c7 * x5) 主题为
一些等式和不等式约束条件

- oMiD

---

也许@solvingPuzzles可以帮助我！ - oMiD

当有人在问题开头解释为什么它与类似的问题不同，这是令人耳目一新的。 - Dennis Meng

@Dennis Meng，抱歉，我不明白你的意思，我的问题不够清楚吗？ - oMiD

完全不是。我只是注意到你在一开始提到了为什么这个问题与其他问题不完全相同。这是一件好事。 :) - Dennis Meng

@AlexanderTorstling，我不明白如何使用它，你能解释一下吗？ - oMiD

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总是大于等于这两个表达式，因此也总是大于等于最大表达式的总和。当正确地最小化x6时，x6将会收敛到最大表达式的值上。因此，在最小化后，这两种形式是等效的。

- Alexander Torstling

---

谢谢你非常清晰的解释，我完全明白了 :) - oMiD