How to assign N numbers into M pack that minimize some target function?

Question

I have N(for example 30) integer numbers V[i], and M(for example 8) packs, each pack have an expected value P[j].

I want to assign each integer number to one pack, the following expression calculate the difference between the sum of V[k] that in pack j and the expected value of pack j.

diff[j] = abs(P[j] - sum(V[k] that in pack j))

The target is to find the best solution that minimize sum(diff[j]).

I don't know what's the type of this kind of problem. Can this be solved by Linear programming, or is it a NP-Complete problem?

Answer 1

Regardless of whether this is NP-hard or not, you may be able to efficiently solve your problem for the problem instances you need using easily accessible integer programming software. For your problem, you could define x_{ij} to define if X[i] is assigned to group j. You would then also define variables d_j, which are the diff[j] in your formulation. Then your model is:

min_{x, d} \sum_{j=1}^M d_j
s.t.       d_j >= P[j] - \sum_{i=1}^N X[i]x_{ij} \forall j
           d_j >= \sum_{i=1}^N X[i]x_{ij} - P[j] \forall j
           \sum_{j=1}^M x_ij = 1 \forall i
           x_{ij}\in \{0, 1\}

This is a mixed integer optimization model, which can be solved, for instance, using the lpsolve or lpSolveAPI packages in R or the intlinprog function in MATLAB.