# Multi-dimensional Knapsack with added one-per-group constraint

I have some sets (A, B, ...) each containing some vectors (e.g. [1, 0, -1]). How can I pick exactly one vector per set such that they sum to a specified target vector?

For example:

A: { [1, 0, -1], [3, 0, 0], ... }
B: { [0, -1, -1], [2, -1, 0], ... }

Target: [3, -1, -1]

Solutions:

1) A=[1, 0, -1], B=[2, -1, 0]
2) A=[3, 0, 0], B=[0, -1, -1]


I think this is a variation of the multi-dimensional knapsack problem with the added 'one-per set' constraint. Has this been written about anywhere?

For my domain, there are 30 sets each containing 50 vectors with 30 dimensions. These vectors are sparse with ~80% zeroes. There is at most one negative number per vector.

Any pointers to research papers or proposed algorithms would be hugely appreciated.

Thanks.

Let $A_{i,j}$ be the $j$th vector in the $i$th set. Define zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means you have picked the $j$th vector from the $i$th set. Then you have constraints of the form
$$\sum_{i,j} A_{i,j} x_{i,j} = t$$
where $t$ is the target vector. (Notice that this is a sum of vectors, so it actually turns into 30 different equations, one per dimension.) Also to ensure that you pick exactly one element from each set, we have
$$\sum_j x_{i,j} = 1$$
for every $i$. Then send that to an ILP solver.