在整数线性规划中使用最小值/最大值

Question

我正在尝试设置一个线性规划模型，其中目标函数会对决策变量与它们相应系数的乘积中的max施加额外权重。

有没有一种方法可以在线性规划模型的目标函数内部使用min或max算子？

示例：

Minimize
    (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) 
subject to
    #some arbitrary integer constraints:
    x1 >= ...
    x1 + 2*x2 <= ... 
    x3 >= ...
    x1 + x3 == ...

请注意，(c4 * max(c1*x1, c2*x2, c3*x3))是我关心的“额外权重”项。我们用c4表示“额外权重”系数。此外，请注意，在这个例子中x1、x2和x3是整数。

我认为上述内容可能超出了线性规划提供的范围。然而，也许有一种方法可以通过修改/重新格式化将其转换成有效的线性规划问题？

如果此问题完全超出了线性规划的范围，也许有人可以推荐一种更适合这种类型问题的优化方法？（任何允许我避免手动枚举和检查所有可能解决方案的方法都会很有帮助。）

- solvingPuzzles

Answer 1

添加一个辅助变量，比如x4，并带有以下限制：

x4 >= c1*x1
x4 >= c2*x2
x4 >= c3*x3  
Objective += c4*x4

- fairidox

---

做得非常好，@justaname。发帖者应该注意新变量x4不一定是整数。 - Ram Narasimhan

只有在最大化函数的最小值或最小化函数的最大值时，这种技术才能奏效。如果需要最小化最小函数或最大化最大函数，则需要添加额外的二进制变量和大M系数。 - Greg Glockner

@solvingPuzzles 你需要使用大M系数。 - Greg Glockner

嗨@statBeginner，你找到解决min over min / max over max问题的方法了吗？我也恰好需要解决这个问题，任何信息都将不胜感激。 - daydayup

min/min的一个简单示例：如果你有： min z，其中z=min(x1,x2,x3)，则写成：min z 其中 z >= x1-M b1，z >= x2-M b2，z >= x3-M b3，b1+b2+b3=2且b1、b2、b3均为二进制。 - Greg Glockner