Finding the highest producing combination within a budget.

Unless somebody here is going to solve the P versus NP problem* the only way to calculate the highest return is to calculate all of the possible combinations which meet your criteria.

Depending on just how much you've simplified your problem this could be quite a major undertaking and take quite a long time to code, test and run.

Perhaps you could give us a few more details and we can at least tell you just how horrible it's likely to be to work out an answer - are there only 3 categories? How many products are in each category? How many from each category might you want to pick?

* Of course, there is a $1,000,000 prize for solving this, so it's not like there's no incentive to try

Hi Andrew, thanks for your swift response!

As I mentioned, I really am an Excel amateur, so I'm not sure I realised how difficult this task might be!

In answer to your questions, there are 5 categories. The final list is still subject to change, but no more than 15 products per category. And I will need 1 product from category 1, 2 from categories 2 and 3, and 1 product from categories 4 and 5.

In reply to Richard: there's no fixed limit to the amount of the budget each category can take up, there is just an overall budget. So it could be that almost all of the budget is allocated to one category, with the small remainder spread across the other categories, or it could be an even split - whichever offers the highest total return (based on the projections).

Hope that made sense!

I was assuming that the project has an absolute budget which can not be exceeded irrespective of the return.

So (simplifying) if we have three type 1 items priced at $250, $500 and $1,000 and have to pick one within a $750 budget then we can exclude item #3.

If we then have three type 2 items priced as per type 1 then we can again exclude item #3, but the inclusion/exclusion of item #2 is conditional on the type 1 item picked (or, if you prefer, the inclusion of type 1 item#2 is dependent on the type 2 item selected).

So, if we're only picking one item from each type we have the combinations:

Type 1, Type 2, Result
1,1,Valid
1,2,Valid
1,3,Invalid
2,1,Valid
2,2,Invalid
2,3,Invalid
3,1,Invalid
3,2,Invalid
3,3,Invalid

Obviously once you get into >2 types and multiple selections for each type the number of results increases exponentially.

Originally Posted by jimmy_fowler

In answer to your questions, there are 5 categories. The final list is still subject to change, but no more than 15 products per category. And I will need 1 product from category 1, 2 from categories 2 and 3, and 1 product from categories 4 and 5.

Just to give you an idea of the scale of this; reading the above as where you require 2 products from a category you required exactly 2, and not 0, 1 or 2, and excluding picking the same product twice as being a valid choice then there are over 32,000,000 possible combinations.

Even generating that many combinations is problematic, because you can't just dump them onto a single Excel sheet for quick (?) comparison.

Originally Posted by Andrew-R

Just to give you an idea of the scale of this; reading the above as where you require 2 products from a category you required exactly 2, and not 0, 1 or 2, and excluding picking the same product twice as being a valid choice then there are over 32,000,000 possible combinations.

Even generating that many combinations is problematic, because you can't just dump them onto a single Excel sheet for quick (?) comparison.

Hi Andrew - this was my concern. If it's not possible, or extremely difficult, then no problem.

It's possible, it's probably not even that difficult to do, but each solution requires three data fields - one to hold the selected combination, one to give the budget expenditure of that combination and one to give the net yield of that combination.

The obvious way of doing it is to loop through each possible combination and write that combination to a working sheet. With a limit of one million rows per sheet you'd end up with a sheet with ever row used for 99 columns, you'd then have to apply an algorithm to calculate the optimum solution (you can't just use a MAX of 33 columns, because there's a likelihood of tied results, in which case you'd want to use some other criteria (perhaps overall budget) to resolve the ties.

At 1/1000th of a second for each combination you're looking at Excel churning away for getting on for 10.5 hours to calculate a result, and that's assuming that it doesn't decide to crash out because of the size of the working sheet.

So, doable, certainly and I'd even have a crack at it, if you want, but whether it would be practical for you is really up to what you think.

Originally Posted by Richard Buttrey

Or am I missing something simple here?

You're missing the possibility that selecting an item of one type with a high return may exclude other high return items of other types.

Going back to my previous example - if the $500 item of type 1 has a yield of 10, compared to 5 for the $250 item, but the type 2 $500 item has a yield of 20 then selecting the $500 item for type 1 will exclude the maximum yield scenario.

Perhaps Solver could be of use?

Alf