在整数线性程序内使用min/max [英] Using min/max *within* an Integer Linear Program

问题描述

我正在尝试建立一个线性程序，其中目标函数为决策变量乘以各自系数后的max增加额外的权重.

I'm trying to set up a linear program in which the objective function adds extra weight to the max out of the decision variables multiplied by their respective coefficients.

考虑到这一点，有没有办法在线性程序的目标函数之内内使用min或max运算符?

With this in mind, is there a way to use min or max operators within the objective function of a linear program?

示例:

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

Note that (c4 * max(c1*x1, c2*x2, c3*x3)) is the "extra weight" term that I'm concerned about. We let c4 denote the "extra weight" coefficient. Also, note that x1, x2, and x3 are integers in this particular example.

我认为以上内容可能不在线性编程提供的范围之内.但是，也许有一种方法可以将其修改/重新格式化为有效的线性程序?

I think the above might be outside the scope of what linear programming offers. However, perhaps there's a way to hack/reformat this into a valid linear program?

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

If this problem is completely out of the scope of linear programming, perhaps someone can recommend an optimization paradigm that is more suitable to this type of problem? (Anything that allows me to avoid manually enumerating and checking all possible solutions would be helpful.)

推荐答案

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

Add in an auxiliary variable, say x4, with constraints:

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

这篇关于在整数线性程序内使用min/max的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！