Optimizing Billing with Maths: Find the Most Cost-Effective Plan for Resources

[bundabrg]

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 later work out the difference between this and their original planitems to work out what they pay or get refunded but that's not relevant for this question.

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

 

[bundabrg]

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