求纸浆目标函数最大值的最小值

Question

我试图用纸浆来得到以下目标函数的最小值U(X)，

其中x_{f,i,v}是二进制值

当把目标函数设置为pulp.LpProblem时，我在写max()时遇到了问题

我所做的是使用python内部函数max()，但它给了我一个错误。似乎它不能用来制浆

    for each_sfc in self.SFCs:
        vnf_id_list = list()
        for each_VNF in each_sfc.VNF_list:
            vnf_id_list.append(str(each_VNF.ID))

        new_sfc_vars = LpVariable.dicts(
            name='X',
            indexs=vnf_id_list,
            lowBound=0,
            upBound=1,
            cat='Continuous'
        )

        for each_key in new_sfc_vars.keys():
            new_sfc_vars[each_key] = 1 - new_sfc_vars[each_key]

        self.sfc_vars.append(new_sfc_vars)

    self.LP_model = LpProblem(
        name="Static backup",
        sense=LpMinimize
    )

    for each_SFC, each_vars in zip(self.SFCs, self.sfc_vars):
        self.LP_model.objective += each_SFC.backup_cost * max(each_vars.values())
    print(self.LP_model.objective)

如何将max()与纸浆一起使用，或者如何重新编写代码

Answer 1

这是一个非常基本的问题

1. max()不是线性的。线性表达式看起来像a1*x1+a2*x2+...。纸浆仅用于线性模型，因此它只允许在目标和约束中使用线性表达式。请注意，某些建模工具具有max功能，但它们通常会在引擎盖下对此进行线性化

2. 对于像min sum(i, max(j, x(i,j))这样的构造，一个非常标准的公式是

   min sum(i, y(i))
   y(i) >= x(i,j)  for all i,j 
   

3. 只要查阅任何LP教科书即可。它将解释这一提法。这通常被称为minimax