使用 Python Pulp 不允许最佳解决方案时出错

Question

我有以下优化问题：

受制于

其中 = {0,1}（二进制变量）。

当我在 Pulp 中实现时：

from pulp import *
x1 = pulp.LpVariable('x1', cat=LpBinary)
x2 = pulp.LpVariable('x2', cat=LpBinary)
x3 = pulp.LpVariable('x3', cat=LpBinary)
x4 = pulp.LpVariable('x4', cat=LpBinary)

prob = pulp.LpProblem('x1+x2+2*x3+x4', pulp.LpMaximize)
prob += lpSum([x1, x2, 2*x3, x4])
prob += lpSum([x1, x2, x3, x4]) == 2
prob.solve()

我得到了、、和的解决方案。但是，我想禁止这种解决方案，在 Pulp 中添加另一个约束为 as:

prob += lpSum([x1, x3]) < 2

但是由于我在 prob.solve() 中有一个虚拟变量，所以我没有得到好的解决方案。我应该使用另一个约束还是我做错了什么？

Answer 1

当你运行prob += lpSum([x1, x3]) < 2时，你得到以下错误：

Traceback (most recent call last): File "xyz.py", line 13, in prob += lpSum([x1, x3]) < 2 TypeError: '<' not supported between instances of 'LpAffineExpression' and 'int'

这是 pulp 包，告诉您不能添加严格的不等式，这是优化求解器的标准要求。由于您所有的变量都是二进制值，<2 与 <=1 相同，进行此更改将使求解器满意：

prob += lpSum([x1, x3]) <= 1
prob.solve()
print(x1.value(), x2.value(), x3.value(), x4.value())
# 0.0 1.0 1.0 0.0

所以现在你得到一个不同的解决方案，相同的 objective 值为 3（x2=1 和 x3=1）。

如果您想输出所有可能的解决方案，您可以使用循环来不断添加约束以禁止最优解，直到最优 objective 值发生变化：

from pulp import *
x1 = pulp.LpVariable('x1', cat=LpBinary)
x2 = pulp.LpVariable('x2', cat=LpBinary)
x3 = pulp.LpVariable('x3', cat=LpBinary)
x4 = pulp.LpVariable('x4', cat=LpBinary)

prob = pulp.LpProblem('x1+x2+2*x3+x4', pulp.LpMaximize)
prob += lpSum([x1, x2, 2*x3, x4])
prob += lpSum([x1, x2, x3, x4]) == 2
prob.solve()
print(x1.value(), x2.value(), x3.value(), x4.value())

opt = prob.objective.value()
while True:
    prob += lpSum([x.value() * x for x in [x1, x2, x3, x4]]) <= 1 + 1e-6
    prob.solve()
    if prob.objective.value() >= opt - 1e-6:
        print(x1.value(), x2.value(), x3.value(), x4.value())
    else:
        break  # No more optimal solutions

这会产生预期的输出：

# 1.0 0.0 1.0 0.0
# 0.0 1.0 1.0 0.0
# 0.0 0.0 1.0 1.0

Answer 2

要找到所有解决方案，您需要进行以下修改

while True:
    prob += lpSum([x for x in [x1, x2, x3, x4] if x.value() >= 0.99]) <= sum([x.value() for x in [x1, x2, x3, x4]]) -1
    prob.solve()
    if prob.objective.value() >= opt - 1e-6:
        print(x1.value(), x2.value(), x3.value(), x4.value())
    else:
        break  # No more optimal solutions

使用 Python Pulp 不允许最佳解决方案时出错

Error disallowing the optimal solution using Python Pulp

mathematical-optimization

linear-programming

pulp