Real life puzzle

[StepOne]

This is a real life problem for which I dont' have the answer! I'm trying to work out a solution to the following problem.

For a certain mobile phone tariff there are three 'bundles' available to buy.

100 International (UK to any other country) minutes - £15
500 International minutes - £50
1000 International minute - £100

I have a list of handsets, each of which has a number of international minutes used per month (on average) and the cost of those minutes. The question is - for each handset, what is the optimum number of bundles to buy? (Assuming that for future months they will use the same number of minutes at the same cost.....!)

You don't need to cover all minutes by a bundle - it may be that it works out cheaper to leave some minutes Out of Bundle. E.g. if a handset used 510 minutes at a cost of £1020 (£2 per minute) then the best solution would be one 500 minute bundle for £50, and 10 minutes left out of bundle for £20 - a total spend of £70.

My question is - is there a neat and elegant solution for calculating the optimum number of bundles for each handset? I have an Excel solution, but it is lengthy, and clunky, and I'm not sure it is always correct! It just seems like the sort of problem for which there might already exist a known optimum solution.

[SteelCamel]

First, we can ignore the 1000 minute bundles – there’s no difference between buying 1000 minutes and buying 2x 500 minutes. So we just need to know the number of 100 minute and 500 minute bundles.

Also it makes no sense to buy more than three of the 100-minute bundles, since you can pay less for more minutes by buying the 500-minute ones. And of course you can only buy whole, non-negative numbers of bundles...

So we’re just looking for the tipping points where it makes sense to buy one more bundle.

For zero minutes, you obviously buy zero bundles of either type for zero pounds. At £2 per minute, 8 minutes will be £16. So for 7 minutes or less, buy no bundles. For 8 minutes, buy a 100 minute bundle.
Our next tipping point is at 108 minutes, where it’s cheaper to buy two 100-minute bundles. Then 208 minutes, where it’s cheaper to buy three.
So far we have:
0-7 minutes – no bundles
8-107 minutes – 100 minute bundle
108-207 minutes – 2x 100 minute bundle
208-?? - 3x 100 minute bundle

As indicated previously, it makes no sense to buy four 100-minute bundles, so our next tipping point is at £50 – which is 303 minutes (£45 for the bundles and £6 for the extra minutes), where we should buy a 500 minute bundle.
Now the pattern repeats, as you buy more 100-minute bundles as needed:
208-302 minutes – 3x 100 minute
303-507 minutes – 1x 500 minute
508-607 minutes – 1x 500 and 1x 100 minute
608-707 minutes – 1x 500 and 2x 100 minute
708-802 minutes – 1x 500 and 3x 100 minute
803-1007 minutes – 2x500 minute (or 1x 1000 minute, the cost is the same)
...and it continues to repeat in the same pattern indefinitely.

Incidentally your example is not the optimum, as for 510 minutes it’s cheaper to buy a 500 minute and a 100 minute bundle for £65 than to have 10 minutes outside the bundle at £70. The out-of-bundle minutes are so expensive compared to the bundles it very quickly tips into buying another bundle being better.

[StepOne]

Hi SC,

Thanks for the response - it does make things a lot simpler ignoring the 1000 minute bundles (or, at least, do the calculations for 500 minute bundles, then converting to 1000 at the end is trivial).

The missing piece is that the rate for International Calls is not always £2 a minute - it depends where you are calling. There could be handsets with 200 minutes of calls costing £14, so they would be better with no bundles.

I'm trying to solve this in Excel, so what I really want is s formula that tells me for 'x' minutes called at a cost of 'y' pence, how many 500 minute bundles should I buy. Another similar formula should then be able to tell me how many hundred minute bundles.

StepOne

[Gengulphus]

Thanks for the response - it does make things a lot simpler ignoring the 1000 minute bundles (or, at least, do the calculations for 500 minute bundles, then converting to 1000 at the end is trivial).

The missing piece is that the rate for International Calls is not always £2 a minute - it depends where you are calling. There could be handsets with 200 minutes of calls costing £14, so they would be better with no bundles.

I'm trying to solve this in Excel, so what I really want is s formula that tells me for 'x' minutes called at a cost of 'y' pence, how many 500 minute bundles should I buy. Another similar formula should then be able to tell me how many hundred minute bundles.

For general problems of this type, it's basically known (or to be precise, very strongly suspected) that there is no simple formula. The branch of mathematics concerned with such problems in general is called "integer programming", and if one looks at the Wikipedia page on the subject, one rapidly comes across terms such as "NP-complete" and "NP-hard". Those terms basically say that if the general integer programming problems can be solved reasonably efficiently, such as by a simple formula, so can an enormous number of other problems that people have spent a lot of effort on, trying to find reasonably efficient solutions, without success. Those problems include (for instance) breaking all the cryptosystems used to make electronic financial transactions secure...

However, that doesn't preclude getting formula solutions to sufficiently simple integer programming problems, and your example looks sufficiently simple to me. Specifically, for your problem as originally stated, as SteelCamel has pointed out it can be reduced to asking to reduce the cost 2A+15B+50C for A 'bundles' of 1 minute, B bundles of 100 minutes and C bundles of 500 minutes to a minimum, subject to the number of minutes A+100B+500C being at least x. And as SteelCamel has also pointed out, we know that whatever the value of x, A <= 7 and B <= 3, since a purchase of 8 single minutes can have the number of minutes increased and the cost reduced by instead buying a 100-minute bundle, and similarly for a purchase of 4 100-minute bundles by instead buying a 500-minute bundle.

That tells us that we only need to consider the 32 combinations of A and B with 0 <= A <= 7 and 0 <= B <= 3. For each of them, calculate the number of minutes x - A - 100B that we have to cover with 500-minute bundles: if it's <= 0, we need no 500-minute bundles; otherwise we need ROUNDUP((x - A - 100B)/500,0) 500-minute bundles. I.e. for each of the 32 combinations of A and B, we can calculate the minimum value of C that will cover x minutes of calls. That gives us 32 (A,B,C) candidates for the solution, (at least) one of which must be the minimum solution, so calculate the cost 2A+15B+50C for each of those 32 candidates and choose one with the lowest cost. That would certainly be feasible to calculate with a fairly simple collection of Excel formulae (and getting it down to just one formula is probably possible, though it might be a bit tricky!).

Using knowledge of the specific numbers in your problem as originally stated, we can reduce the number of candidates. Specifically, we know that the number of minutes covered by the 100-minute and 500-minute bundles is always a multiple of 100, and every multiple of 100 minutes is achievable with at least one combination of 100-minute and 500-minute bundles. Since purchases of single minutes are so uncompetitively priced compared with purchases of bundles, it's clear that there are only two reasonable ways one might cover x minutes: either buy the next multiple of 100 down using bundles and buy (x MOD 100) single minutes, or buy the next multiple of 100 up using bundles and no single minutes. Combining that with the knowledge that it's never worth buying more than 7 single minutes, we can deduce that there are at most two possibilities for the number A of single minutes we buy and the N hundred minutes we buy in bundles, calculated as follows:

a = x MOD 100
n = (x-a) / 100
First possibility is A = 0 and N = n+1
IF (a <= 7) THEN second possibility is A = a and N = n; ELSE second possibility doesn't exist

For each of those one or two possibilities, it's then a matter of how most cheaply to buy N hundreds of minutes with bundles. The answer is fairly easy because the 500-minute bundles are a simple multiple of the size of the 100-minute bundles: buy as many 500-minute bundles as one can within the constraint of buying no more than N hundreds of minutes, then if one has 400 minutes still to buy, buy another 500-minute bundle, but if one has 300 or fewer minutes still to buy, buy them as the appropriate number of 100-minute bundles. I.e. process each possibility further as follows:

b = N MOD 5
c = (N-b) / 5
IF (b = 4) THEN B = 0 and C = c+1; ELSE B = b and C = c

This gives us one or two possibilities for (A,B,C), so finish by calculating the cost 2A+15B+50C of the single possibility, or for each of the two and choosing the one with the lowest cost. Or one can do some further analysis of the entire procedure to conclude that the possibility with A = a and N = n is only the least-cost solution if there are 0, 1 or 2 'spare' hundreds over a multiple of 500 and a <= 7, or 3 such 'spare' hundreds and a <= 2, leading to the calculation:

a = x MOD 100
n = (x-a) / 100
b = n MOD 5
c = (n-b) / 5
IF ((b <= 2 AND a <= 7) OR (b = 3 AND a <= 2)) THEN A = a and B = b and C = c;
ELSE A = 0; IF (b = 4) THEN B = 0 and C = c+1; ELSE B = b+1 and C = c;
cost = 2*A + 15*B + 50*C;

(I'll leave the job of translating that into Excel formulae as an exercise for the reader!)

One can in principle do a similar analysis for more complicated problems - but very roughly speaking, either the number of possibilities your calculations have to calculate the cost of and choose the minimum from or the number of cases in your code are liable to grow very rapidly as you add extra complications such as further bundles (especially if the various bundles on offer are quite competitively priced - this particular case was quite easy to analyse because (among other reasons) the prices 200p, 15p and 10p per minute of the three options differ markedly), minutes to different countries being priced differently, etc. It's that potentially very rapid growth in the work that needs doing as the problems become more complex that makes general integer programming problems so hard in the worst case.

By the way, as your example of a handset with 200 minutes for £14 shows, adding an option which is a sufficiently good bargain compared with other options can actually reduce the complexity of the problem: basically, adding that one option effectively eliminates two existing options from consideration. So the effective and apparent complexities of a specific problem may be quite different...

So to sum up, for a specific problem of this type, there may well be a reasonably easy solution that one can arrive at by analysis using the specific numbers involved. But adding extra complications is liable to make the solution more difficult, possibly much more difficult. So I'm afraid "missing pieces" may be very significant, quite possibly completely changing the solution...

Gengulphus

[modellingman]

This is a real life problem for which I dont' have the answer! I'm trying to work out a solution to the following problem.

For a certain mobile phone tariff there are three 'bundles' available to buy.

100 International (UK to any other country) minutes - £15
500 International minutes - £50
1000 International minute - £100

I have a list of handsets, each of which has a number of international minutes used per month (on average) and the cost of those minutes. The question is - for each handset, what is the optimum number of bundles to buy? (Assuming that for future months they will use the same number of minutes at the same cost.....!)

You don't need to cover all minutes by a bundle - it may be that it works out cheaper to leave some minutes Out of Bundle. E.g. if a handset used 510 minutes at a cost of £1020 (£2 per minute) then the best solution would be one 500 minute bundle for £50, and 10 minutes left out of bundle for £20 - a total spend of £70.

My question is - is there a neat and elegant solution for calculating the optimum number of bundles for each handset? I have an Excel solution, but it is lengthy, and clunky, and I'm not sure it is always correct! It just seems like the sort of problem for which there might already exist a known optimum solution.

Hi SC,

Thanks for the response - it does make things a lot simpler ignoring the 1000 minute bundles (or, at least, do the calculations for 500 minute bundles, then converting to 1000 at the end is trivial).

The missing piece is that the rate for International Calls is not always £2 a minute - it depends where you are calling. There could be handsets with 200 minutes of calls costing £14, so they would be better with no bundles.

I'm trying to solve this in Excel, so what I really want is s formula that tells me for 'x' minutes called at a cost of 'y' pence, how many 500 minute bundles should I buy. Another similar formula should then be able to tell me how many hundred minute bundles.

StepOne

One of Excel's powerful problem solving features is the bundled add-in Solver. https://support.microsoft.com/en-us/off ... 3e45925040

Your problem is of the general form

Minimise: a1*x1 + a2*x2 + a3*x3 + ....
Subject to: m1*x1 + m2*x2 + m3*x3 +... >= M

The x's are your decision variables (the numbers of bundles of each type that you require), the a's are the unit cost's per "bundle" and the m's are the minutes provided in each "bundle". Some "bundles" will be based on the standard international tariffs of the country (or countries?) that the phone is required to call.

This type of formulation is known as Linear Programming. The thing being minimised (or alternatively maximised) is generally known as the objective function and the "subject to" is known as a constraint. Typical linear programming problems generally have more than one constraint. Where the decision variables are additionally constrained to take integer values the term Integer Programming is used or Mixed Integer-Linear Programming where some but not all decision variables must be integer. When the objective function or constraints are not a linear combination of the decision variables the term Non-Linear Programming is used.

Solver can handle many Linear, Integer and Non-Linear style of Programming problems particularly when they involve only a handful of decision variables. It takes a little bit of getting used to but there is plenty of helpful stuff available on the web. It has been a very long time since I had cause to use Solver so I haven't taken the time to re-acquaint myself with it and test it against your phone problem. However, if this is a genuine real life problem, with worthwhile cost savings from getting it right then it might be worth you spending the effort on investigating and understanding Solver's capabilities.

[ReformedCharacter]

One of Excel's powerful problem solving features is the bundled add-in Solver. https://support.microsoft.com/en-us/off ... 3e45925040

Your problem is of the general form

Minimise: a1*x1 + a2*x2 + a3*x3 + ....
Subject to: m1*x1 + m2*x2 + m3*x3 +... >= M

The x's are your decision variables (the numbers of bundles of each type that you require), the a's are the unit cost's per "bundle" and the m's are the minutes provided in each "bundle". Some "bundles" will be based on the standard international tariffs of the country (or countries?) that the phone is required to call.

This type of formulation is known as Linear Programming. The thing being minimised (or alternatively maximised) is generally known as the objective function and the "subject to" is known as a constraint. Typical linear programming problems generally have more than one constraint. Where the decision variables are additionally constrained to take integer values the term Integer Programming is used or Mixed Integer-Linear Programming where some but not all decision variables must be integer. When the objective function or constraints are not a linear combination of the decision variables the term Non-Linear Programming is used.

Solver can handle many Linear, Integer and Non-Linear style of Programming problems particularly when they involve only a handful of decision variables. It takes a little bit of getting used to but there is plenty of helpful stuff available on the web. It has been a very long time since I had cause to use Solver so I haven't taken the time to re-acquaint myself with it and test it against your phone problem. However, if this is a genuine real life problem, with worthwhile cost savings from getting it right then it might be worth you spending the effort on investigating and understanding Solver's capabilities.

Thank you that's interesting and useful!

RC

[StepOne]

Thanks for all the replies - especially the comment about Solver, which I need to look into a bit more.

The above query is only part of the problem, because there are other bundles (SMS, Roaming, etc) and other tariffs available with different options. I have an Excel model which works for many of these, but it's basically brute force - it looks at applying N and N+1 of each bundle, then work through all the options, so I end up with 9 options, take the cheapest, and if two are the same price, choose the one with the most minutes. I've often thought that there must be a better way.

The model was created years ago (by someone else) and has been changed and updated by several people over the years, with different tariffs and different bundles, and each worksheet does things in a different way, so I am trying to look for a generic solution that I could apply across the board.

It's one of those jobs where it is simpler to tweak the existing Heath Robinson tool (which works) than to re-write the whole thing, but occasionally I am tempted to do the latter

Thanks Again,
StepOne