任何解决具有约束的选择问题的有效解算器

Question

我正在处理一个包选择问题。我必须对最终结果进行限制，比如"选定产品中排名前三的品牌应占50%以下"。

我试着在Pulp上实现这一点。但CBC求解器似乎不支持这种约束。请帮帮我。我怎么能施加这样的约束？还是应该切换到另一个解算器？

Answer 1

这在一定程度上取决于；排名前三的品牌"；如果你的意思是三个最大的x[i]的总和应该小于总数的50%，那么这可以线性化如下：

y1 >= x[i]              for all i
y2 >= x[i]-M*delta1[i]  for all i
y3 >= x[i]-M*delta2[i]  for all i
y1+y2+y3 <= sum(i,x[i])/2
sum(i, delta1[i]) = 1
sum(i, delta2[i]) = 2
delta1[i],delta2[i] ∈ {0,1} 

CBC可以解决这个问题。这里M是一个足够大的常数(称为big-M(，delta1、delta2是二进制变量。请注意，y1、y2和y3是最大三个值的边界，因此解释这些值可能并不总是显而易见的。基本上，这些值的定义是：

y1 : variable at least as large as the largest x[i]
y2 : variable at least as large as the second largest x[i]
y3 : variable at least as large as the third largest x[i]

还有其他更好的配方(但这一个更直观[对我来说](。

一种更简单的方法是在CVXPY中使用sum_largest(x,k)，例如

sum_largest(x,3) <= sum(x)/2