title: Solving the multiple-choice multidimensional knapsack
body: <p>I am trying to solve some (relatively easy) instances of the multiple-choice multidimensional knapsack problem (where there are groups of items where only one item per group can be obtained and the weights of the items are multi-dimensional as well as the knapsack capacity). I have two questions regarding the formulation and solution:</p>
  
  <ol>
  <li>If two groups have different number of items, is it possible to fill in the groups with smaller number of items with items having zero profit and weight=capacity to express the problem in a matrix form? Would this affect the solution? Specifically, assume I have optimization programs, where the first group (item-set) might have three candidate items and the second group has two items (different than three), i.e. these have the following form:</li>
  </ol>
  
  <p>maximize (over x_ij) {v_11 x_11 + v_12 x_12 + v_13 x_13 + </p>
  
  <pre><code>                 v_21 x_21 + v_22 x_22}
  </code></pre>
  
  <p>subject to {w^i_11 x_11 + w^i_12 x_12 + w^i_13 x_13 + w^i_21 x_21 + w^i_22 x_22 &lt;= W^i, i=1,2</p>
  
  <pre><code>        x_11 + x_12 + x_13 = 1, x_21 + x_22 = 1, x_ij \in {0,1} for all i and j.
  </code></pre>
  
  <p>Is it OK in this scenario to add an artificial item x_23 with value v_23 = 0 and w^1_23 = W^1, w^2_23 = W^2 to have full products v_ij x_ij (i=1,2 j=1,2,3)? </p>
  
  <ol start="2">
  <li>Given that (1) is possible, has anyone tried to solve instances using some open-source optimization package such as cvx? I know about cplex but it is difficult to get for a non-academic and I am not sure that GLPK supports groups of variables.</li>
  </ol>