algorithm - 背包算法的变体

Question

我有一个项目列表，a, b, c,...，每个项目都有一个重量和一个值。

“普通”背包算法将找到最大化所选项目值(value)的项目选择，同时确保重量低于给定约束。

我遇到的问题略有不同。我希望最小化该值(通过使用该值的倒数很容易)，同时确保权重至少给定约束的值，不小于或等于约束。

我已经尝试通过普通的背包算法重新路由这个想法，但这无法完成。我希望有另一种我不知道的组合算法可以做到这一点。

Answer 1

德语wiki它被正式化为:

finite set of objects U
w: weight-function
v: value-function

w: U -> R
v: U -> R
B in R    # constraint rhs

Find subset K in U subject to:
    sum( w(u) <= B ) | all w in K
such that: 
    max sum( v(u) )  | all u in K

所以不存在像非负性这样的限制。

只需使用负权重、负值和负 B。基本概念是:

 sum( w(u) ) <=  B | all w in K
<->
-sum( w(u) ) >= -B | all w in K

所以在你的情况下:

classic constraint: x0 + x1 <=  B    | 3 + 7 <= 12 Y | 3 + 10 <= 12 N
becomes:           -x0 - x1 <= -B    |-3 - 7 <=-12 N |-3 - 10 <=-12 Y 

因此对于给定的实现，它取决于软件是否允许这样做。就优化问题而言，没有问题。您案例的整数规划公式与经典公式一样自然(并且有界)。

基于整数规划的Python Demo

代码

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

""" INSTANCE """
weight = np.random.randint(50, size = 5)
value = np.random.randint(50, size = 5)
capacity = 50

""" SOLVE """
n = weight.shape[0]
model = CyClpSimplex()
x = model.addVariable('x', n, isInt=True)
model.objective = value                            # MODIFICATION: default = minimize!
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       # MODIFICATION
cbcModel = model.getCbcModel()
cbcModel.logLevel = True
status = cbcModel.solve()
x_sol = np.array(cbcModel.primalVariableSolution['x'].round()).astype(int)  # assumes existence

print("INSTANCE")
print("    weights: ", weight)
print("    values: ", value)
print("    capacity: ", capacity)
print("Solution")
print(x_sol)
print("sum weight: ", x_sol.dot(weight))
print("value: ", x_sol.dot(value))

小备注

• 这段代码只是一个演示，使用了一些低级的库，还有其他可用的工具可能更适合(例如 windows:pulp)
• 这是来自 wiki 的经典整数规划公式如上所述修改
• 它将很好地扩展，因为底层求解器非常好
• 正如所写，它正在解决 0-1 背包问题(只需要更改变量边界)

小看核心代码:

# create model
model = CyClpSimplex()

# create one variable for each how-often-do-i-pick-this-item decision
# variable needs to be integer (or binary for 0-1 knapsack)
x = model.addVariable('x', n, isInt=True)

# the objective value of our IP: a linear-function
# cylp only needs the coefficients of this function: c0*x0 + c1*x1 + c2*x2...
#     we only need our value vector
model.objective = value                            # MODIFICATION: default = minimize!

# WARNING: typically one should always use variable-bounds
#     (cylp problems...)
#  workaround: express bounds lower_bound <= var <= upper_bound as two constraints
#  a constraint is an affine-expression
#  sp.eye creates a sparse-diagonal with 1's
#  example: sp.eye(3) * x >= 5
#           1 0 0 -> 1 * x0 + 0 * x1 + 0 * x2 >= 5
#           0 1 0 -> 0 * x0 + 1 * x1 + 0 * x2 >= 5
#           0 0 1 -> 0 * x0 + 0 * x1 + 1 * x2 >= 5
model += sp.eye(n) * x >= np.zeros(n)              # could be improved
model += sp.eye(n) * x <= np.ones(n)               # """

# cylp somewhat outdated: need numpy's matrix class
# apart from that it's just the weight-constraint as defined at wiki
# same affine-expression as above (but only a row-vector-like matrix)
model += np.matrix(-weight) * x <= -capacity       # MODIFICATION

# internal conversion of type neeeded to treat it as IP (or else it would be 
LP)
cbcModel = model.getCbcModel()
cbcModel.logLevel = True
status = cbcModel.solve()

# type-casting
x_sol = np.array(cbcModel.primalVariableSolution['x'].round()).astype(int)  

输出

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 4.88372 - 0.00 seconds
Cgl0004I processed model has 1 rows, 4 columns (4 integer (4 of which binary)) and 4 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 0 integers unsatisfied sum - 0
Cbc0038I Solution found of 5
Cbc0038I Before mini branch and bound, 4 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I After 0.00 seconds - Feasibility pump exiting with objective of 5 - took 0.00 seconds
Cbc0012I Integer solution of 5 found by feasibility pump after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective 5, took 0 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 5 to 5
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:                5.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

INSTANCE
    weights:  [37 43 12  8  9]
    values:  [11  5 15  0 16]
    capacity:  50
Solution
[0 1 0 1 0]
sum weight:  51
value:  5