Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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?]

share|improve this answer
    
I'm sorry, I was unclear. They must exceed the threshold, but I'm trying to minimize this excess. I'm also trying to use all the numbers we have. So in a group of (a,b,c) and threshold t, I can group a,b > t and c > t (for instance). Unfortunately, wouldn't the answer you gave yield me only (a,b) OR c; but not a,b AND c? I'm trying to use all the numbers in $a_n$. –  markovchain May 14 '13 at 11:38
    
OK, I'm lost. What do you mean by using all the numbers? If I read the first sentence of your question, then using all the numbers is a contradiction (for me at least), because you want to use a combination of these numbers the sum of which is greater than the threshold but by a minimal amount. This implies that you are looking for a subset of all values $a_n$ whose sum is as small as possible, given that it exceeds the threshold. Anyway, I'm changing my answer according to my new understanding of the question. –  Matt L. May 14 '13 at 19:59
    
Hi! I'm sorry I just got back now, but I do want to use all the numbers. The answer I want to get is a set of subsets. So the $a_n$ I have will be grouped in $s_1, s_2, s_3$, with the intersection of each subset with each other being null, and the union of all the sets being $a_n$. I hope I was clearer. –  markovchain May 17 '13 at 10:27
    
And the threshold is only a limit on the sum of the subsets, but the individual values of the elements of $a_n$ are generally expected to always be lower than the threshold. –  markovchain May 17 '13 at 10:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.