max - 在整数线性规划*内*使用最小/最大

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 是整数。

我认为上述内容可能超出了线性规划提供的范围。然而，也许有一种方法可以将其破解/重新格式化为有效的线性程序？

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

Answer 1

添加一个辅助变量，例如 x4，并带有约束:

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