快速背包求解器解决大问题
Fast Knapsack Solver For big problems
我想用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)
但是当我们将其扩大到：
import knapsack
weight = np.random.randint(10, size = 1000)
value = np.random.randint(10, size = 1000)
capacity = 500
knapsack.knapsack(weight, value).solve(capacity)
程序卡住并报错。我想知道是否有一些背包问题的实现，我们可以在其中陈述诸如计算 10 秒之类的东西 return 我是迄今为止找到的最佳解决方案，这可能吗？
这里是 0-1 背包的 0-1 整数编程小原型方法！
此代码：
- 并不是每件事都做得很完美！
- 例如constraints vs. bounds（后者效率更高；但懒得为此再次检查 cylp；过去的问题）
- 对windows的支持不多！
- windows 用户：选择 pulp，它带来了相同的求解器（恕我直言，最好的免费开源 MIP 求解器）；虽然那里的造型看起来很不一样！
- 没有调整！
- 有界/无界背包版本只需修改边界即可轻松处理
此处的示例仅解决了 OP 使用 1 的 PRNG 种子定义的一个问题，需要 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))
输出
Welcome to the CBC MILP Solver
Version: 2.9.9
Build Date: Jan 15 2018
command line - ICbcModel -solve -quit (default strategy 1)
Continuous objective value is -1965.33 - 0.00 seconds
Cgl0004I processed model has 1 rows, 542 columns (542 integer (366 of which binary)) and 542 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 1 integers unsatisfied sum - 0.333333
Cbc0038I Pass 1: suminf. 0.25000 (1) obj. -1965 iterations 1
Cbc0038I Solution found of -1965
Cbc0038I Branch and bound needed to clear up 1 general integers
Cbc0038I Full problem 1 rows 542 columns, reduced to 1 rows 128 columns
Cbc0038I Cleaned solution of -1965
Cbc0038I Before mini branch and bound, 540 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I After 0.02 seconds - Feasibility pump exiting with objective of -1965 - took 0.01 seconds
Cbc0012I Integer solution of -1965 found by feasibility pump after 0 iterations and 0 nodes (0.02 seconds)
Cbc0038I Full problem 1 rows 542 columns, reduced to 1 rows 2 columns
Cbc0001I Search completed - best objective -1965, took 0 iterations and 0 nodes (0.02 seconds)
Cbc0035I Maximum depth 0, 362 variables fixed on reduced cost
Cuts at root node changed objective from -1965.33 to -1965.33
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: -1965.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock seconds): 0.02
Total time (CPU seconds): 0.02 (Wallclock seconds): 0.02
[0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0
0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1
0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 0
0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0
0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1
0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0
1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0
0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1
0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1
0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1
1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1
0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0
0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0
0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1
0]
500
1965
我想用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)
但是当我们将其扩大到：
import knapsack
weight = np.random.randint(10, size = 1000)
value = np.random.randint(10, size = 1000)
capacity = 500
knapsack.knapsack(weight, value).solve(capacity)
程序卡住并报错。我想知道是否有一些背包问题的实现，我们可以在其中陈述诸如计算 10 秒之类的东西 return 我是迄今为止找到的最佳解决方案，这可能吗？
这里是 0-1 背包的 0-1 整数编程小原型方法！
此代码：
- 并不是每件事都做得很完美！
- 例如constraints vs. bounds（后者效率更高；但懒得为此再次检查 cylp；过去的问题）
- 对windows的支持不多！
- windows 用户：选择 pulp，它带来了相同的求解器（恕我直言，最好的免费开源 MIP 求解器）；虽然那里的造型看起来很不一样！
- 没有调整！
- 有界/无界背包版本只需修改边界即可轻松处理
此处的示例仅解决了 OP 使用 1 的 PRNG 种子定义的一个问题，需要 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))
输出
Welcome to the CBC MILP Solver
Version: 2.9.9
Build Date: Jan 15 2018
command line - ICbcModel -solve -quit (default strategy 1)
Continuous objective value is -1965.33 - 0.00 seconds
Cgl0004I processed model has 1 rows, 542 columns (542 integer (366 of which binary)) and 542 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 1 integers unsatisfied sum - 0.333333
Cbc0038I Pass 1: suminf. 0.25000 (1) obj. -1965 iterations 1
Cbc0038I Solution found of -1965
Cbc0038I Branch and bound needed to clear up 1 general integers
Cbc0038I Full problem 1 rows 542 columns, reduced to 1 rows 128 columns
Cbc0038I Cleaned solution of -1965
Cbc0038I Before mini branch and bound, 540 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I After 0.02 seconds - Feasibility pump exiting with objective of -1965 - took 0.01 seconds
Cbc0012I Integer solution of -1965 found by feasibility pump after 0 iterations and 0 nodes (0.02 seconds)
Cbc0038I Full problem 1 rows 542 columns, reduced to 1 rows 2 columns
Cbc0001I Search completed - best objective -1965, took 0 iterations and 0 nodes (0.02 seconds)
Cbc0035I Maximum depth 0, 362 variables fixed on reduced cost
Cuts at root node changed objective from -1965.33 to -1965.33
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: -1965.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock seconds): 0.02
Total time (CPU seconds): 0.02 (Wallclock seconds): 0.02
[0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0
0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1
0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 0
0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0
0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1
0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0
1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0
0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1
0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1
0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1
1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1
0 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0
0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0
0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1
0]
500
1965