3

I'm having trouble coming up with an approach that isn't n^2 for this problem. Here's a contrived, simplified version I've come up with:

Let's say you're a company that needs 4 employees to launch in a new city, a manager, two salespeople, and a customer support rep, and you magically know how much impact every candidate will have and how much salary they require to take the job. Your table of potential employees looks something like this:

Name           Position       Salary     Impact
Adam Smith     Manager        60,000     11
Allison Brown  Salesperson    40,000     9
Brad Stewart   Manager        55,000     9
...etc (thousands of records)

What algorithmic approach can be taken to find the maximum "impact" while still filling all the positions and remaining under, say, a 200,000 budget?

Thanks!

6
  • 13
    This is a variant of the well-known Knapsack problem (en.wikipedia.org/wiki/Knapsack_problem). And as Wikipedia states, use dynamic programming, branch&bound or a combination of both.
    – Doc Brown
    Apr 10 '14 at 5:57
  • 2
    Just as a remark, I think that your first sentence is not correct. You should consider yourself happy if you find an approach that is n^2, given that a brute force approach has a complexity of 2^n.
    – Renaud M.
    Feb 4 '15 at 14:42
  • @DocBrown That should be an answer =)
    – Ixrec
    Apr 5 '15 at 13:18
  • Are you doing this many times on the same data set? Do you just need a "good enough" result, not perfection? If both answers are "yes", you can get a quick solution by keeping the data in tables sorted by Impact/Salary and by Impact. Apr 5 '15 at 17:25
  • @Ixrec: no, it should not, answers which are not much more than a pointer to a different article are not welcome here on PSE.
    – Doc Brown
    Apr 5 '15 at 20:34
1

I'd use Integer Linear Programming (which, in essence, is constraint programming, which is what you are doing) to solve this kind of problem, using CPLEX in conjunction with Visual Studio. As stated in your post, the objective of your program will be to maximize a goal given a set of constraints (e.g. total budget must be less than $200,000).

To get started and if you have not previously configured CPLEX to work with Visual Studio, consult this guide. For a template of problems that need to maximize a goal, check the following tutorial handout that contains code samples that you can modify to your criteria.

0

Ultimately you're going to need to write a "cost" function, and then use some algebraic technique to find the maximum(s).

If you wanted a quick-and-somewhat-dirty answer, you could use a Genetic Algorithm to propose, test, and incrementally improve answers until you got a good one. But it wouldn't be guaranteed to be the best. However, it could provide relatively quick turn-around if you wanted to tweak the formula and search again.

1
  • Genetic algorithm is good when you have many variables to optimize, and there is no clear "winner" solution. In this case, you have only two variables. There are better algorithms in these cases, however your answer isn't "wrong", so I won't penalize you for it.
    – Neil
    Jun 9 '14 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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