Maths for the masses

Yesterday, I was a bit poorly, so I decided to use the time I was indisposed to stretch my brain a bit, the upshot of it was a spreadsheet with more than a wee bit of data on it, and this problem:

I won’t say exactly what it’s for (a point if you can guess correctly!), but essentially I need to choose 15  “objects” from over 500. Each of these objects has 27 values attached to it, 25 of which are “cost” values (which must each be considered separately), one is a “worth” value, and one is a “choice” value (i.e., it’s 1 if I choose it and 0 if I don’t). I need to maximise the total “worth” of the items I choose, subject to the 26 restrictions listed above (one of which, number 6, is that I must choose exactly 15 objects).

Those of you familiar with OR will see that this is a variation on the Knapsack Problem [which is concerned with finding a way of maximising value while keeping the total cost under a certain amount, given a list of available items] (except I’m using it in 27 dimensions).

Sadly I naively assumed that I could just plug everything into a formula and it would give me the answer. Not so, for it needs to check every possible combination in order to verify its maximality (the problem is NP-complete), and would take about 20 years to solve on my Macbook Pro.

That the problem is formulated is a good start, though. Maybe I’ll have found a better way of solving it come mid-august, when it may be needed again…

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s