Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed the threshold, but we want to minimize this excess.
For example, if I have $5$, $15$, $4$, $8$, $16$, $12$, and $9$; and my threshold is $17$. How do I find the combination of numbers with minimum deviation from this threshold?
One way I'm thinking about expressing the question is to minimize the sum of the squares of the differences between the threshold and the sum of that group. Like, if my groups were $5$ and $16$; 8 and 15; 9, 4, and 12; then I want to minimize this way: $$[(16 + 5)^2 - 17^2] + [(15 + 8)^2 - 17^2] + [(12 + 4 + 9)^2 - 17^2] = 728$$
But the groups could be grouped like this, so this is a better combination:
$$[(16 + 4)^2 - 17^2] + [(15 + 5)^2 - 17^2] + [(12 + 4 + 6)^2 - 17^2] = 417$$
How do I find the best combination in the general case? Preferably, if someone could show me the linear program formulation, that would be great. I think this is most likely an integer program though, with binary variables. Am I in the right direction when I say:
$$Min Z = \sum_n {(a_nx_n)^2 - t^2}$$ $$st$$ $$\sum_n{a_nx_n} > t$$ $$x_n = 1,0$$
The above seems to be wrong because some of the x's will be set to 0, but I'm trying to use all the numbers I have, but grouped in different ways. But I'm out of ideas on how to address that.
Added: To be clearer, I want to use all the numbers in $a_n$. I don't want to just pick a few numbers from it. The situation I have is I'm trying to assign jobs to people, and all jobs have to be worked. The $a_n$ represent money they make for doing 1 unit of the job (piecework rate), and the threshold is the minimum wage.
Also, in extension, how do I ban/disallow specific combinations from appearing? For example, if I wanted to ban $a_5 = 16$ and $a_7 = 9$ because the processes they represent can't happen simultaneously, so that due to that constraint, if that combination was part of the optimal solution, I'd have to change my solution; how do I do that? Would it be:
$$x_5 + x_7 = 1$$
Again, it doesn't seem to be that above because one off the x's will be set to 0, but I need all the numbers to be used. The program would be good if I was just finding the combination of numbers that would reach the threshold, but I'm trying to use all the numbers and collectively trying to minimize all their deviations.
I am (still) not sure if I understand the problem correctly. I'm considering the following problem: given a set of numbers $a_n$, find the group of numbers whose sum is minimal, given that it exceeds a certain threshold.
$$\min_{x_n}\sum_n x_na_n\\ \text{s.t. } \sum_n x_na_n \ge t,\quad x_n\in\{0,1\}$$
where $t$ is the threshold and $x_n$ are the unknown weights.
[Need for clarification: I do not understand how you want to use all the numbers. What are the allowed weights then in the sum? Is the threshold supposed to be a lower limit on the (weighted) sum of $a_n$ or on $a_n$ themselves?]