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
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.
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