python - 使用 python cplex 的 0-1 背包

Question

我正在尝试解决 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 来运行这个问题。这个问题的解决办法是

x = [[0 1 0 0 0]
     [0 0 0 0 1]];
profit = 10 + 40
       = 50

问题的数学表述为:

我正在尝试使用 Python CPLEX 获得与上面相同的解决方案。以下代码是我尝试解决该问题的方法，但它不正确。我不确定如何解决:

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()

Answer 1

你的问题是你没有表明你解决的程序是MIP。我不知道如何在 Python 下使用 2d 变量，但以下方法有效:

import numpy as np
import cplex
from cplex import Cplex
from cplex.exceptions import CplexError

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 = [ [ 'x'+str(i)+str(j) for j in range(1,n+1) ] for i in range(1,k+1) ]
xvar = xvar[0] + xvar[1]
profit = profit[0] + profit[1]

types = 'B'*n*k

ub = [1]*n*k
lb = [0]*n*k

try:
    prob = cplex.Cplex()
    prob.objective.set_sense(prob.objective.sense.maximize)

    prob.variables.add(obj = profit, lb = lb, ub = ub, types = types, names = xvar )

    rows = [[ xvar, weight+weight ]]
    rows = [[ xvar, weight+weight ],
            [ xvar[:5], [1]*5 ],
            [ xvar[5:], [1]*5 ],
           ]

    prob.linear_constraints.add(lin_expr = rows, senses = 'LEE', rhs = [capacity,1,1], names = ['r1','r2','r3'] )

    prob.solve()
    print
    print "Solution value  = ", prob.solution.get_objective_value()
    xsol = prob.solution.get_values()
    print 'xsol = ', np.reshape(xsol, (k,n) )

except CplexError as exc:
    print(exc)

我得到的答案:

Solution value  =  50.0
xsol =  [[ 0.  1.  0.  0.  0.]
         [ 0.  0.  0.  0.  1.]]