我试图解决一个0-1背包问题的小修改,其中每个项目都是从中选择一个值的向量,而不是使用Python Cplex的标量。这是Mixed integer problem的变体。我为这个问题写了一个IBM OPL的解决方案,但无法想出如何使用Python Cplex来解决它。我使用IBM OPL的解决方案是:
int Capacity = 100; // Capacity of the knapsack
int k = 2; // Number of items
int n = 5; // Number of values
range values = 1..n;
range items = 1..k;
// parameters
int profit[items][values] = [[ 5, 10, 20, 20, 20], // only one item should be selected from this list
[ 5, 20, 25, 30, 40]]; // only one item should be selected from this list
int weight[values] = [ 10, 20, 50, 70, 80]; // Corresponding weights
// decision variable x[i][j]=1 if the jth item is selected
dvar boolean x[items][values];
// objective function
maximize sum(i in items, j in values) x[i][j] * p[i][j];
// constraints
subject to{
sum(i in items, j in values) x[i][j] * w[j] <= Capacity;
forall(i in items) sum(j in values) x[i][j] <= 1;
}
我们可以将此问题作为oplrun -v knapsack.mod
运行。解决这个问题的办法是
问题的数学公式是:
我正在尝试使用pythoncplex获得与上面相同的解决方案。下面的代码是我试图解决的问题,但它是不正确的。我不知道该怎么解决:
import cplex
capacity = 100 # Capacity of the cache
k = 2 # Number of items
n = 5 # Number values for each item
profit = [[5, 10, 20, 20, 20],
[5, 10, 25, 30, 40]]
weight = [10, 20, 50, 70, 80]
xvar = [] # Will contain the solution
def setupproblem(c):
c.objective.set_sense(c.objective.sense.maximize)
# xvars[i][j] = 1 if ith item and jth value is selected
allxvars = []
for i in range(k):
xvar.append([])
for j in range(n):
varname = "assign_" + str(i) + "_" + str(j)
allxvars.append(varname)
xvar[i].append(varname)
# not sure how to formulate objective
c.variables.add(names=allxvars, lb=[0] * len(allxvars),
ub=[1] * len(allxvars))
# Exactly one value must be selected from each item
# and the corresponding weights must not exceed capacity
# Not sure about this too.
for j in range(k):
thevars = []
for i in range(n):
thevars.append(xvar[i][j])
c.linear_constraints.add(
lin_expr=[cplex.SparsePair(thevars, [1] * len(thevars))],
senses=["L"],
rhs=capacity)
def knapsack():
c = cplex.Cplex()
setupproblem(c)
c.solve()
sol = c.solution
if __name__ == "__main__":
knapsack()
你的问题是你没有指出你解决的程序是MIP。我不知道如何在Python下使用2d变量,但是以下方法可以工作:
我得到的答案是:
^{pr2}$相关问题 更多 >
编程相关推荐