PuLP中的弹性子问题如何用作约束条件？

Question

PuLP中的弹性子问题如何用作约束条件？

pythoncombinatoricslinear-programmingcplexpulp

9

在Python的PuLP中，线性规划约束可以转化为弹性子问题。

http://www.coin-or.org/PuLP/pulp.html?highlight=lpsum#elastic-constraints

解决子问题可以优化距离目标值的距离。

当然，目标值是这个子问题的最优解，但弹性化的整个重点在于我们认为这个解可能是不可行的。

如何将子问题纳入整个问题？我尝试将其添加到问题中，就像添加约束一样，但这会引发类型错误。我尝试将其放在目标函数中，但这也不起作用。

我在上面的文档或这里托管的示例中找不到任何东西：

https://code.google.com/p/pulp-or/wiki/OptimisationWithPuLP?tm=6

这是我制定的子问题：

capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
    sense=-1, rhs=30, name=str(random.random()))
stretch_proportion = 30/50
elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
    proportionFreeBoundList=[1,stretch_proportion])

这是我认为最接近将其纳入LP目标的方法：

def sub(m):
    capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
        sense=-1, rhs=30, name=str(random.random()))
    stretch_proportion = 30/50
    elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
        proportionFreeBoundList=[1,stretch_proportion])
    elasticCapacity.solve()
    return elasticCapacity.isViolated()

...

prob += lpSum( [ x[m][n] * reduce(op.add, map(D2, [i.l for i in n.items], [j.l for j in n.items]))\
    for n in N for m in M ] ) + 50 * sub(m)

- Bret Fontecchio

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GrayOnGray · Accepted Answer

以下是简短答案，一个可行示例的草图:

创建问题并添加硬约束和目标。

prob = LpProblem("My Problem", LpMinimize)
....

在完成上述步骤后，定义软（弹性）约束并使用 pulp.prob.extend() 将其添加到问题中，如下所示：

c_e_LHS = LpAffineExpression([(var1,coeff1), (var2,coeff2)])   # example left-hand-side expression
c_e_RHS = 30   # example right-hand-side value
c_e_pre = LpConstraint(e=el_constr_LHS, sense=-1, name='pre-elastic', rhs=c_e_RHS)   # The constraint LHS = RHS
c_e = c_e_pre.makeElasticSubProblem(penalty=100, proportionFreeBoundList=[.02,.02])   # The definition of the elasticized constraint 
prob.extend(c_e)   # Adding the constraint to the problem

在这一点上，问题已经被修改以包括软（弹性）约束条件，并且您可以解决它。$\qed$。

以下是更长的答案：此问题已在pulp-or-discuss Google组中回答，详见添加弹性约束。我根据该讨论和PuLP文档网站上混合问题的较长公式创建了下面的示例，以满足自己的需求。

首先，您需要创建问题：

from pulp import *
prob = LpProblem("The Whiskas Problem", LpMinimize)

创建一个食材列表：

Ingredients = ['CHICKEN', 'BEEF', 'MUTTON', 'RICE', 'WHEAT', 'GEL']

创建了每种成分成本的字典：

costs = {'CHICKEN': 0.013, 
         'BEEF': 0.008, 
         'MUTTON': 0.010, 
         'RICE': 0.002, 
         'WHEAT': 0.005, 
         'GEL': 0.001}

创建了一个包含每种配料中蛋白质百分比的字典：

proteinPercent = {'CHICKEN': 0.100, 
                  'BEEF': 0.200, 
                  'MUTTON': 0.150, 
                  'RICE': 0.000, 
                  'WHEAT': 0.040, 
                  'GEL': 0.000}

创建了每个成分脂肪含量的字典：

fatPercent = {'CHICKEN': 0.080, 
              'BEEF': 0.100, 
              'MUTTON': 0.110, 
              'RICE': 0.010, 
              'WHEAT': 0.010, 
              'GEL': 0.000}

创建了一个每种成分中纤维含量的字典：

fibrePercent = {'CHICKEN': 0.001, 
                'BEEF': 0.005, 
                'MUTTON': 0.003, 
                'RICE': 0.100, 
                'WHEAT': 0.150, 
                'GEL': 0.000}

创建了每种成分盐分百分比的字典：

saltPercent = {'CHICKEN': 0.002, 
               'BEEF': 0.005, 
               'MUTTON': 0.007, 
               'RICE': 0.002, 
               'WHEAT': 0.008, 
               'GEL': 0.000}

创建一个变量'prob'来存储问题数据：

prob = LpProblem("The Whiskas Problem", LpMinimize)

创建了一个名为'ingredient_vars'的字典来包含所引用的变量：

ingredient_vars = LpVariable.dicts("Ingr",Ingredients,0)

添加目标：

prob += lpSum([costs[i]*ingredient_vars[i] for i in Ingredients]), "Total Cost of Ingredients per can"

创建硬性约束（这里是我的示例与文档中的示例开始分歧的地方）：

c1 = lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "PercentagesSum"
c2 = lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "ProteinRequirement"
c3 = lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "FatRequirement"
c4 = lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "FibreRequirement"
c5 = lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "SaltRequirement"

添加硬性约束：

for con in [c1,c2,c3,c4,c5]:
    prob += con

将约束的左侧表达式定义为弹性化：

c6_LHS = LpAffineExpression([(ingredient_vars['GEL'],1), (ingredient_vars['BEEF'],1)])

定义需要弹性化的约束条件：明胶和牛肉的总和不超过30%。

c6= LpConstraint(e=c6_LHS, sense=-1, name='GelBeefTotal', rhs=30)

定义弹性约束：

c6_elastic = c6.makeElasticSubProblem(penalty = 100, proportionFreeBoundList = [.02,.02])

这是向问题添加弹性（即软）约束的方法：

prob.extend(c6_elastic)

解决问题：

prob.writeLP("WhiskasModel.lp")
prob.solve()

输出最优解：

for v in prob.variables():
    print v.name, "=", v.varValue

如果您尝试更改惩罚和边界，您可以验证其按照所述方式工作。

附注：我的理解是问题的标题可能会误导。添加弹性子问题相当于在目标函数中添加一些成本项，对应于“软约束”。软约束不是约束 - 它是目标函数中一组成本项的简写。