如何在 PuLP 中基于先前的解决方案施加约束？

Question

所以我有这个混合整数程序，其中我的指标 x 在 0 或 1 中取决于是否使用该项目。我想根据以下代码中的约束使包中物品的价格最大化。

我的问题是，我想把这个过程重复有限次，每次都用这个解对下一个time/round做进一步的约束.

价格每次 time/round 波动，因此需要包装不同的物品。但是，我只允许 一个免费每次更改 我运行求解器。对于最后一个解决方案集的每个额外更改，每个项目都会受到 -100 的惩罚。玩具示例：因此，如果最后一个解决方案是 [0,0,1,1,0,0,0,0,0,0] 并且新解决方案是 [1,1,0,0,0,0,0, 0,0,0] 那么由于与上一轮相比有 2 个变化，因此将在 objective 中产生 -100 的惩罚。如果它更改为 [0,1,0,1,0,0,0,0,0,0] 则不会受到惩罚。

如何在 objective 中施加此惩罚并施加 1 个自由更改约束？

初始程序如下：

items = [i for i in range(len(df))]
price = df['price'].to_dict()
volume = df['volume'].to_dict() 
weight = df['weight'].to_dict()


prob = LpProblem('mip',LpMaximize)
x = LpVariable.dicts("items", items, 0, 1, LpBinary)

#objective
prob += lpSum([(price[i]*x[i]) for i in items])

#constraints
prob += lpSum([x[i] for i in items]) = 10
prob += lpSum([weight[i] * x[i] for i in items]) <= 1000
prob += lpSum([volume[i] * x[i] for i in items]) <= 5000

prob.solve()

#to get the solution in a list for reuse
current_solution = [x[i].varValue for i in items]

我考虑过在 var[i] 中使用 prices = -100 的虚拟项目，但无法实现。有什么帮助吗？非常感谢。

Answer 1

不容易。

我会尝试类似的方法：

（1）引入一个二元变量d[i] ∈ {0,1}和约束条件：

 -d[i] <= x[i] - x0[i] <= d[i]

其中 x0 是上一个解决方案。（这必须在 PuLP 中实现为两个不同的约束。此外，我们实际上可以放松 d 以在 0 和 1 之间连续：它将自动成为二进制。）

(2) 添加一个变量n和约束：

  n = sum(i, d[i])

(3) 添加正变量n1 >= 0和约束

  n1 >= n - 1

(4) 在 objective

中添加一个术语

 -100*n1

（我们想最小化 100*n1 所以我添加了减号，因为你的 obj 正在最大化）。

如何在 PuLP 中基于先前的解决方案施加约束？

How to impose constraints based on previous solution in PuLP?

python

optimization

mathematical-optimization

pulp

mixed-integer-programming