有没有办法在 PuLP 中检索下一个最优解？

Question

下面列出了一个非常简单的背包问题。

df 的样本如下所示：

| weight | item  | profit |
|--------|-------|--------|
| 1      | item1 | 3.977  |
| 2      | item2 | 3.126  |
| 3      | item3 | 2.698  |
| 4      | item4 | 2.607  |
| 5      | item5 | 2.569  |

objective是选择4个总重量>=10的商品，利润最大化。我要解决的代码如下：

prob = LpProblem("Weight",LpMaximize)
player_vars = [pulp.LpVariable(f'Item_{row.item}', cat='Binary') for row in df.itertuples()]

# total items  constraint
prob += pulp.lpSum(player_var for player_var in player_vars) == 4

# total weight constraint
prob += pulp.lpSum(df.Seed.iloc[i] * player_vars[i] for i in range(len(df))) >= 10

# problem
prob += pulp.lpSum([df.profit.iloc[i] * player_vars[i] for i in range(len(df))])

# solve and print the status
prob.solve()
print(LpStatus[prob.status])
    
#print results
    for i in range(len(df)):
        if player_vars[i].value() == 1:
            row = df.iloc[i]
            print(row.item, row.weight,row.profit)

我想知道是否有办法使用 PuLP 获得第二好的答案等等？谢谢！

Answer 1

一种方法是通过添加附加约束来禁止现有的最佳解决方案来重新解决问题。例如，假设原始问题的解决方案存储为 player_vars_soln，然后您将添加一个约束：

prob += pulp.lpSum(player_vars_soln[i]*player_vars[i] for i in range(len(df))) <= 3

有没有办法在 PuLP 中检索下一个最优解？

Is there a way to retrieve the next best optimal solution in PuLP?

python

optimization

pulp