如何在 PULP 中构建复杂约束 python

Question

我正在尝试解决具有额外复杂性的背包式优化问题。

这是一个简单的例子。我正在尝试 select 5 项价值最大化的项目。 2 件物品必须是橙色的，一件必须是蓝色的，一件必须是黄色的，一件必须是红色的。这很简单。但是，我想添加一个约束条件，即 selected 黄色、红色和橙色项目只能与 selected 蓝色项目有一个共同的形状。

import pandas as pd
from pulp import *
import re

BlueMatch = lambda x: 1 if x=='blue' else 0
YellowMatch = lambda x: 1 if x=='yellow' else 0
RedMatch = lambda x: 1 if x=='red' else 0
OrangeMatch = lambda x: 1 if x=='orange' else 0

data = [['A', 'blue', 'circle', 0.454], 
    ['B', 'yellow', 'square', 0.570],
    ['C', 'red', 'triangle', 0.789],
    ['D', 'red', 'circle', 0.718],
    ['E', 'red', 'square', 0.828],
    ['F', 'orange', 'square', 0.709],
    ['G', 'blue', 'circle', 0.696],
    ['H', 'orange', 'square', 0.285],
    ['I', 'orange', 'square', 0.698],
    ['J', 'orange', 'triangle', 0.861],
    ['K', 'blue', 'triangle', 0.658],
    ['L', 'yellow', 'circle', 0.819],
    ['M', 'blue', 'square', 0.352],
    ['N', 'orange', 'circle', 0.883],
    ['O', 'yellow', 'triangle', 0.755]]

example = pd.DataFrame(data, columns = ['item', 'color', 'shape', 'value']) 

example['color'] = example['color'].astype(str)

example['isBlue'] = example.color.apply(BlueMatch)
example['isYellow'] = example.color.apply(YellowMatch)
example['isRed'] = example.color.apply(RedMatch)
example['isOrange'] = example.color.apply(OrangeMatch)

prob  = pulp.LpProblem("complex_napsack", pulp.LpMaximize) 
x = pulp.LpVariable.dicts( "x", indexs = example.index, lowBound=0, upBound=1, cat='Integer', indexStart=[] )

prob += pulp.lpSum([x[i]*example.value[i] for i in example.index ])

prob += pulp.lpSum([x[i]*example.isBlue[i] for i in example.index])==1
prob += pulp.lpSum([x[i]*example.isYellow[i] for i in example.index])==1
prob += pulp.lpSum([x[i]*example.isRed[i] for i in example.index])==1
prob += pulp.lpSum([x[i]*example.isOrange[i] for i in example.index])==2

prob += pulp.lpSum([x[i] for i in example.index ])==5

prob.solve()

total_value = 0
for v in prob.variables():
    if v.varValue == 1.0:
        mystring = re.search('([0-9]*$)', v.name)
        print(v.name, "=", v.varValue)
        ind = int(mystring.group(1))
        print(example.item[ind])
        total_value = example.value[ind] + total_value

print(total_value)

#x_11 = 1.0
#L
#x_13 = 1.0
#N
#x_4 = 1.0
#E
#x_6 = 1.0
#G
#x_9 = 1.0
#J
#4.087

#But, the blue item (G) is a circle,  and both (L) and (N) are also circles.  I only want the red, orange, and yellow items to only have at most one shape in common with the blue item.

#How do I formulate a constraint to do this?

谢谢！

Answer 1

几种方式：

1) 对于每个蓝色项，确保如果选中它，则从非蓝色项中选择的形状不超过 1 个：

for idx in example.index:
  if example.isBlue[idx]:
    prob += pulp.lpSum([x[i] for i in example.index if not example.isBlue[i] and example.shapes[i] == example.shapes[idx]]) <= (1 - x[idx]) * 4 + 1

2) 对于每个形状，请确保如果从该形状中选择了蓝色，则从非蓝色形状中选择的形状不超过 1 个：

for shape in example.shapes.unique():
  prob += pulp.lpSum([x[i] for i in example.index if not example.isBlue[i] and example.shapes[i] == shape]) <= (1 - pulp.lpSum([x[i] for i in example.index if example.isBlue[i] and example.shapes[i] == shape])) * 4 + 1

I am making the right side be 1 when blue is selected and 5 if not (thus not imposing any restriction over the others).

3) 为每个形状解决一个问题，其中您预先定义蓝色的形状，确保不超过 1 个非蓝色选择该形状，然后在所有问题解决方案中保留最佳解决方案。

如何在 PULP 中构建复杂约束 python

How to construct a complex constraint in PULP python

python

mathematical-optimization

linear-programming

pulp