Possible Maths Problem

[Brendan Grieve]

Hi All,

 

I'm busy trying to write a 'smart' billing system, but I'm getting a bit stuck with some of the maths and thought that if someone else looked at what I'm doing you may see a much easier solution.

 

Background: -

First, just a little explanation of how it works.

 

A person has an account that is part of a 'plan'. A plan is made up of zero or more plan items (or options in the plan), and each plan item can provide 0 or more resources.

 

What that means is that if I have the following 3 resources I am selling: -

• Mailbox Resource
• .com Domain Resource
• .net Domain Resource

And in my plan I have the following plan items (options): -

• .Com Domain - $10

• Provides 1 '.com Domain Resource'

• Provides 4 'Mailbox resource'

• .Net Domain - $10

• Provides 1 '.net Domain Resource'
• Provides 4 'Mailbox resource'

• Mailbox - $1

• Provides 1 'Mailbox resource'

So, for example if I had 2 .com domains, and 9 mailboxes, the optimal 'PlanItems' that I should have is:

• 2x '.Com Domain' @ $10 each
• 1x 'Mailbox' @ $1

Total: $21

 

Hope that makes sense. Ultimately a Plan would have hundreds of these options, with the options costing different amounts and providing differing number of resources.

What it means is that I work with resources (they are the service I actually provide), but my customer is given the 'PlanItems' which can provide several resources. In actual fact, the 'smart' part of the billing is that the customer doesn't know about the planitems. They just buy another resource, and the billing system works out the best options for them.

 

 

My Estimate function works like this: -

• Pass in the number of resources we want in total. Ie, 9 mailbox resources, 2 .com resources
• It then works out the optimal (least cost) planoptions that fulfil that critera. Doesn't matter if it provides more resources than requested.

I had hoped that I could simply this to some equations, but for the life of me I can't figure anything that works. What I've had to do is write a recursive function that just tries every combination of planitem in varying amounts, returning the cheapest one.

 

That works fine if I only have a few planitems to choose from, or if the total resources I want is fairly small. Should it get large, it gets messy.

 

For example, with just 3 planitems to choose from, if I made a request of:

• 1000x mailbox resources
• 1x .com resource
• 1x .net resource

Then the recursive function will loop probably (1000/4)^3 (Divided by 4 as the .com and .net provide 4 mailbox resources each, so they should max at 1000/4 worst case scenario).

 

 

Soooo, looking at just 3 plan items, with the above requested resources, I have the following formulas: -

• a = .com Plan Item
• b = .net Plan Item
• c = Mailbox Plan Item

• x = .com Resource
• y = .net Resource
• z = mailbox resource

So:

a = x + 4z

b = y + 4z

c = z

 

Thus my ultimate formula is: -

 

ma + nb + oc = a + b + 1000c

 

IE, what valus of m,n and o provide that solution. And somehow this needs to be weighted so that a and b are both the same weight, with c being 1/10th of the weight (the price).

 

 

Is there a simpler way? Or is the only option to recursively test every option? If recursive tests are the only way then I'll just work on trying to optimize it further.

 

Thanks,

 

Brendan

Edited February 21, 2011 by Brendan Grieve

[imatfaal]

Brendan

 

I must be missing something - cos the way I read your message is that nothing fancy is required (and I think that means I must have read wrongly)

 

For example, with just 3 planitems to choose from, if I made a request of:

• 1000x mailbox resources
• 1x .com resource
• 1x .net resource

Then the recursive function will loop probably (1000/4)^3 (Divided by 4 as the .com and .net provide 4 mailbox resources each, so they should max at 1000/4 worst case scenario).

 

Why need for a recursive function? The .com resource and the .net resource each provide 4 mailbox resources - that's 8; therefore you need 992 mailbox resources. the three plans you have given have only one common feature (the mailboxes); therefore to minimally evaluate cost all you need to do is

 

[# .com]*$10 + [# .net ]*$10 + ([# mailboxes]-[# .com]*4 - [# .net]*4) *$1

 

if the final part is less than one just drop it.

 

The only reason would need to trial and error test is when you have multiple options with multiple crossovers at different pricing. This rapidly becomes difficult.

[Brendan Grieve]

Hi imatfaal,

 

You're right, it is fairly straight forward, especially for the human brain which see's that pattern quite quickly, but trying to write a computer function that does that work is much trickier, unless I'm missing something.

 

For example, what if price of the .net item for example was $2 rather than $10, but all the rest of the items were the same. The total list would then be: -

• .Net Plan Item - Provides 1x .net resource, 4x Mailbox resource - $2
• .Com Plan Item - Provides 1x .com resource, 4x Mailbox resource - $10
• Mailbox Plan Item - Provides 1x Mailbox resource - $1

Now the best option would be to use lots of .Net plan items to fulfill the 1000 mailboxes (-4 for the one we are required to get to fulfill the .com requirement). You'd end up with about 200 .net resources you don't need, but it would be cheaper than even using the Mailbox plan items.

 

Also, there are perhaps 50 different top level domains, so a full plan item list could have about 52 options to choose from (each with their own individual prices + providing differing mailbox resources). There may also be plan items that don't provide any resource that we want, though its trivial to prune them out before hand so that at a minimum all the plan item options are offering at least one resource we want.

 

 

Presently my recursive function tries the following. Assuming 3 plan item options to choose from (a,b,c), it tries: -

0a 0b 0c

0a 0b 1c

0a 0b 2c

... - Till success or adding any more of C does not reduce our resources wanted

0a 1b 0c

0a 1b 1c

0a 1b 2c

... - Till success or adding any more C does not reduce our resources

0a 2b 0c

...

...

1a 0b 0c

1a 0b 1c

 

etc

 

 

If there were 50 plan items to choose from, the number gets very big.

 

 

I guess my main reason for the post is in case I've missed some blinding obvious solution as I've spent too long looking at the problem that I'm too close to it. If the only solution is a recursive function then perhaps I can break that down so I don't need to test every possible combination.

 

Brendan

 

 

UPDATE: Actually something you said has sparked an idea. Perhaps if I split my tests up so I'm only testing individual resources rather than groups, I can then dispense with a recursive function and derive a value quickly. Will think on it.

 

UPDATE2:

Figured out a solution. The missing piece is that I can simply split the resources I want and work on them separately as long as I follow a golden rule: -

• Reduce the solution by the smallest number of resources I need at a time (since we _have_ to solve each one)

So, in my example I would do the following: -

1. Look at the smallest resources I need to solve. In this case its either the .com or the .net as I only need 1 of each. So I pick the .com.
2. Find which plan item solves it for the cheapest price. This is straight algebra.
3. Reduce all the other requested resources by whatever that solution provides. So it would reduce the number of mailbox resources by 4, leaving 996.
4. Repeat till there are no resources left

Edited February 22, 2011 by Brendan Grieve

[imatfaal]

Your update2 enlarged on what I was trying to say - whilst there is only one way of buying .net and .com, there is a very simple solution. You will get real difficulties if you have multiple combinations - with only 3 products I don't think it would ever get too hard to calculate with a fairly simple algorithm, but if you had 20 products and various combinations working out the cheapest plan would be getting close to impossible. Unless I am mistaken this is not a simply scalable problem - the time taken to work out a slightly more complicated problem could be exponentially more than the marginally simpler question.

[Brendan Grieve]

Actually my change solves the problem in linear time related to the number of options and number of requests and not related at all to the size of the request. My brute force method previously took an exponentially higher amount of time based on the size of the request multiplied by how many items and how many options to choose from.

 

I have 83 plan items presently, all of them providing a wide range of options (some providing multiple domains, differing mailboxes, space etc etc), and some with limitations (IE, you can only have a maximum of a certain item etc). The change of looking at one resource at a time, in reverse size order, solving it completely, then adding all the individual solutions together, then removing a few spares at the end, solves it lightning quick.

 

For example, I've just put an estimate that has the following (All the test items here provide 4 mailboxes and cost variying amounts but are higher than just a mailbox on its own). These items are in addition to all my other items I've added back in that provide options, bringing the total plan items available to 90 to choose from: -

• x10000 Mailbox resources
• x3 Domain1 resources
• x1 Domain2 resources
• x5 Domain3 resources
• x10 Domain10 resources
• x5 Domain34 resources
• x55 Domain20 resource

Estimate returns straight away, that the following satisfies this -

• x1 Domain2 Item
• x3 Domain1 Item
• x5 Domain34 Item
• x5 Domain3 Item
• x10 Domain 10 Item
• x55 Domain20 Item
• x9684 Mailbox Item

If I reduce Domain2's price to twice that of the Mailbox item such that it would be cheaper to use that, it gives: -

• x2422 Domain2 Item
• x3 Domain1 Item
• x5 Domain34 Item
• x5 Domain3 Item
• x10 Domain 10 Item
• x55 Domain20 Item

There does not seem to be a limit to the complexity of the request that I can perform (at least without getting silly) and as it works with nearly 100 options to choose from fast enough to be unnoticeable I'm *very* happy!

 

Brendan

Edited February 22, 2011 by Brendan Grieve

[imatfaal]

I don't have the time to check nor the details - but I am pretty sure that complexity of solution time will not scale once you have a decent amount of combination. ie if you only have one way of purchasing .com then that massively eases the problem, ditto with .net.

 

But if you could buy .com with or without .net and with/without mailboxes, and then add in .co.uk (for me!) .org and .ac.uk ;all with various combo plans - then suddenly it becomes an ornery problem