title: 0-1 knapsack using python cplex
body: <p>I'm trying to solve a slight modification of a 0-1 knapsack problem, where each item is a vector of values from which one value is chosen, instead of a scalar using Python Cplex. This is a variant of a <a href="http://www-01.ibm.com/support/knowledgecenter/#!/SS9UKU_12.4.0/com.ibm.cplex.zos.help/UsrMan/topics/discr_optim/mip/02_prob_statement.html" rel="nofollow noreferrer">Mixed integer problem</a>. I wrote a <a href="http://www-01.ibm.com/software/commerce/optimization/modeling/" rel="nofollow noreferrer">IBM OPL</a> solution to this problem, but unable to figure out how to solve it using <a href="http://www-01.ibm.com/support/knowledgecenter/?lang=en#!/SSSA5P_12.6.0/ilog.odms.cplex.help/refpythoncplex/html/cplex._internal._subinterfaces.LinearConstraintInterface-class.html?cp=SSSA5P_12.6.0" rel="nofollow noreferrer">Python Cplex</a>. My solution using IBM OPL is:</p>
  
  <pre><code>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] &lt;= Capacity;
  forall(i in items) sum(j in values) x[i][j] &lt;= 1;
  
  }
  </code></pre>
  
  <p>We can run this problem as <code>oplrun -v knapsack.mod</code>. The solution to this problem is </p>
  
  <pre><code>x = [[0 1 0 0 0]
       [0 0 0 0 1]];
  profit = 10 + 40
         = 50
  </code></pre>
  
  <p>The mathematical formulation of the problem is:</p>
  
  <p><a href="https://i.stack.imgur.com/8FOUg.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8FOUg.png" alt="Knapsack math formulation"></a></p>
  
  <p>I'm trying to get the same solution I got above using Python CPLEX. The following code is my try to solve the problem but it is not correct. I'm unsure of how to solve it:</p>
  
  <pre><code>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()
  </code></pre>