大问题快速背包求解器

Question

我想用Python近似解决大数据集的背包问题。在

现在，我使用的是this implementation，它适用于以下小示例：

import knapsack
weight = np.random.randint(10, size = 10)
value = np.random.randint(10, size = 10)
capacity = 5
knapsack.knapsack(weight, value).solve(capacity)

但当我们把它扩大到：

^{pr2}$

程序只是卡住了并给出了一个错误。我想知道是否有一些背包问题的实现，我们可以声明像计算10秒这样的东西，并返回到目前为止找到的最好的解决方案，这可能吗？在

Answer 1

这里有一个小原型0-1整数规划方法为0-1背包！在

此代码：

• 不是每件事都做得很完美！
  • e、 约束与边界（后者更有效；但懒得再次检查cypp；过去的问题）
• 不支持windows！
  • windows用户：使用pulp，它带来了相同的解算器（imho是最好的免费开源MIP解算器）；尽管建模在那里看起来很不一样！在
• 没有调谐！
  • 注意：CoinOR的Cgl，用于求解器Cbc，支持额外的背包切割！在
  • 如日志所示：示例太简单，无法在其使用中起作用！在
• 有界/无界背包版本只需修改边界即可轻松处理

这里的例子只解决了一个由OP定义的使用PRNG种子1的问题，其中需要0.02秒，但这不是科学测试！NP-hard问题都是关于简单和困难的实例（巨大的差异！）正因为如此，要检查的数据非常重要！我们可以观察到，在这个例子中没有真正的完整性缺口。在

代码

import numpy as np
import scipy.sparse as sp
from cylp.cy import CyClpSimplex
np.random.seed(1)

""" INSTANCE """
weight = np.random.randint(10, size = 1000)
value = np.random.randint(10, size = 1000)
capacity = 500

""" SOLVE """
n = weight.shape[0]
model = CyClpSimplex()
x = model.addVariable('x', n, isInt=True)
model.objective = -value
model += sp.eye(n) * x >= np.zeros(n)  # could be improved
model += sp.eye(n) * x <= np.ones(n)   # """
model += np.matrix(weight) * x <= capacity  # cylp somewhat outdated in terms of np-usage!
cbcModel = model.getCbcModel()  # Clp -> Cbc model / LP -> MIP
cbcModel.logLevel = True
status = cbcModel.solve()
x_sol = np.array(cbcModel.primalVariableSolution['x'].round()).astype(int)  # assumes there is one

print(x_sol)
print(x_sol.dot(weight))
print(x_sol.dot(value))

输出

^{pr2}$