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

Question

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.

Answer 1

One reasonable starting point is to try formulating it as an instance of integer linear programming, and apply an ILP solver. This might not be the best possible algorithm, but it is simple and easy to try.

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.