optimization - Solving the multiple-choice multidimensional knapsack -
i trying solve (relatively easy) instances of multiple-choice multidimensional knapsack problem (where there groups of items 1 item per group can obtained , weights of items multi-dimensional knapsack capacity). have 2 questions regarding formulation , solution:
- if 2 groups have different number of items, possible fill in groups smaller number of items items having 0 profit , weight=capacity express problem in matrix form? affect solution? specifically, assume have optimization programs, first group (item-set) might have 3 candidate items , second group has 2 items (different three), i.e. these have following form:
maximize (over x_ij) {v_11 x_11 + v_12 x_12 + v_13 x_13 +
v_21 x_21 + v_22 x_22} subject {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 <= w^i, i=1,2
x_11 + x_12 + x_13 = 1, x_21 + x_22 = 1, x_ij \in {0,1} , j. is ok in scenario add artificial item x_23 value v_23 = 0 , w^1_23 = w^1, w^2_23 = w^2 have full products v_ij x_ij (i=1,2 j=1,2,3)?
- given (1) possible, has tried solve instances using open-source optimization package such cvx? know cplex difficult non-academic , not sure glpk supports groups of variables.
| | do need exact solution, or approximate mmkp sufficient? – sneftel jul 23 '15 @ 23:03 | ||
| | thank reply. ideally want exact solution. know there greedy solution dominated items removed , items taken in descending order of efficiency try , solve using different methods , compare. – lstavr jul 23 '15 @ 23:45 | ||
| | i have seen exact solutions these quite complicated , not sure if difference in performance worth time implementing these. – lstavr jul 24 '15 @ 0:05 | ||
| | 1: cvx convex-optimization , there should't support integer variables (only if use gurobi/mosek cvx; problem should hard formulate in pure continuously way). glpk may support these, cbc (coin-or branch , cut) should first approach when not using cplex/gurobi. 2: mean group of variables: stuff can described integer variables , solved cbc. no special support needed. 3: if want more these general remarks, should describe problem in more formal way. – sascha jul 26 '15 @ 0:47 | ||
| | @sascha thank lot help. – lstavr aug 18 '15 @ 13:20 |