在整数线性程序中使用min/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