[R] ?currency challenge ?knapsack challenge ?probabilities

Polwart Calum (COUNTY DURHAM AND DARLINGTON NHS FOUNDATION TRUST) calum.polwart at nhs.net
Sun Dec 27 12:08:29 CET 2015

I am currently working on a project that is producing Gigabyte sized vectors that kill R.  It can take 24 hours to run. So frustrating to get that far and have to scale back my inputs and rerun...

The problem i'm trying to solve as i see it is very similar to optimal currency denominations problems combined with a knapsack problem. Let me TRY to explain.

We have a product that we want to manufacture in as few sizes as possible.  like currency if you want 30cents but a 30cent coin doesnt exist you can join multiple products together. (3x10 cent, 25cent +5 cent, etc)

Unlike currency we dont need every value to be possible, we have a list of known values which are effectively related to each other by the next size up being 25% bigger. So for instance 64, 80 100.

We have some rules that say you can't use more than X products combined to make the final size.  A bit like saying never give more than 10 coins as change, so you cant issue 20x5cents for a dollar of change.

All of that fits a standard currency denomination challenge.

We dont need the combinations to be calculated using greedy method. [We will calculate and store as a table]

BUT - we do have a manufacturing limitation that means can manufacture to any whole number size, we cant do smaller than size5. (We dont go as low as that anyway... size 11 is as low as needed).  So different from any currency problem I've seen where the lowest coin size is always a 1 allowing any size to be produced.

So i have three questions I'm trying to answer:

- what is the smallest product range we can make that achieves our rules for max combinations of sizes?

- Is there a more optimal range. Say the smallest range was 4 sizes, for example 5,6,23,40.  Its possible adding a 22 and a 46 to that may actually be cheaper than supplying 2x5 and 2x6 or 2x23...

Currently I'm identifying every possible combination into a matrix.  We have a manufacturing constraint of max size 49 as well.  So i take every end user size possible (from 11 thru to 125).  For each size i then take every combination of possible sizes from 5 to 49 (45 sizes) that we COULD make and work out how i can achieve all the possible end user sizes, discarding any combinations that break our rules for max combinations.

Thats a giant set of for loops.  Once i establish the options we  can apply the manufacturing costs and usage data to find the answer.

For now 45 sizes,combined in any of up to 5 different combinations to do 10 end user sizes is creating vectors too big for R to handle...

Long explanation of the problem, to basically say... has anyone come across a function in R that might simplify this?

Sent from TypeMail<http://www.typeapp.com/r>

On 27 Dec 2015, at 08:00, "Polwart Calum (COUNTY DURHAM AND DARLINGTON NHS FOUNDATION TRUST)" <calum.polwart at nhs.net<mailto:calum.polwart at nhs.net>> wrote:


This message may contain confidential information. If you are not the intended recipient please inform the
sender that you have received the message in error before deleting it.
Please do not disclose, copy or distribute information in this e-mail or take any action in reliance on its contents:
to do so is strictly prohibited and may be unlawful.

Thank you for your co-operation.

NHSmail is the secure email and directory service available for all NHS staff in England and Scotland
NHSmail is approved for exchanging patient data and other sensitive information with NHSmail and GSi recipients
NHSmail provides an email address for your career in the NHS and can be accessed anywhere


	[[alternative HTML version deleted]]

More information about the R-help mailing list