Community Phone, a telecom provider dedicated to flexible plans with easy to access customer support, purchases data, minutes, and texts wholesale from three nationwide telecom providers. These providers sell data in tranches with discontinuous pricing. This presented an optimization challenge for Community Phone, given that end-users are able to share those tranches. Community Phone wanted to purchase data strategically, sharing tranches across end-users. Several variables presented challenges to this goal: end-users consume data continuously, end-users consume different amounts of data each month, Community Phone must purchase data from the three providers before learning how much data the end-users consumed that month, and end-users switch to Community Phone throughout the month, so Community Phone does not even know how many end-users will be consuming data at the point when Community Phone must purchase data from the nationwide carriers. Furthermore, Community Phone can purchase data on an unlimited basis from one of the three carriers, but this plan costs a pretty penny.

Here is how Community Phone’s in-house developers, Dhruv Mohnot and Philip Nicol, approached the problem. First, they investigated the data-usage histories of the end-users.

The first wrinkle in the purchasing strategy is that end-users consume different amounts of data each month. To combat this problem, Community Phone’s developers needed to model future data-usage, erring on the side of over-estimating so that Community Phone does not purchase too little data from the nationwide providers, thereby incurring overage fees.

This was stellar news for Community Phone. An end-user’s future data usage is best predicted by his or her data usage in the immediately preceding month.

Now that Community Phone’s developers understand how to predict future data usage, they need to understand the best method for purchasing data from the nationwide providers. Data is purchased on a monthly basis, so a reevaluation of how much Community Phone should purchase would be done on a monthly basis as well.

## Calculating an Optimal Partition

Suppose it is the day before the cycle with the carrier resets. At this point, Community Phone has N customers. The task is to assign a plan to everybody that minimizes costs while ensuring that the enough data is purchased. It is useful to view each person as an individual customer with some internal data plan. So a family of three can be viewed as 3 individual customers each with their own individual plan.

The possible plans at our carrier are (in gb) 1, 3, 5, 7, 10, or unlimited. Let Nk represent the number of customers with a k-gigabyte internal plan. Similarly, Nunlimited is the number of customers with the unlimited plan. So we have:

The cost of the monthly plans can be expressed as

Clearly, we want to choose the Nk and Nunlimited so as to minimize N. However, we also need to ensure that we buy enough data so as to avoid overage charges!

Each individual has a unique ID. For simplicity, assume that the IDs are numbered from 1 to N. Let M(i) be the predicted consumption of customer i for the next cycle. M(i) can be estimated using standard statistical techniques. Notice that

is the predicted consumption for all customers.

With this notation in place, we can formulate the objective as minimizing the cost function C subject to the following constraints:

The notation i ∈ {N1,N3,N5,N7,N10} refers to IDs for customers who are assigned something other than the unlimited plan. Then the second constraint ensures that the data allotted to customers on a fixed size plan is greater than what they are predicted to consume. Of course, M(i) is predicted, and we could be off the true monthly consumption. We account for this with the ε term, higher ε means we are more safe from overage charges.

## Solving the Problem

Notice that there are 2N possibilities for which customers are assigned unlimited plans. However, searching the vast majority of these 2N subsets are useless. If a customer uses less than 7 GB, than it never makes sense to put them on unlimited because the 7 GB fixed size plan is 3 dollars cheaper. Moreover, if there are k unlimited plans, then it is optimal to assign them to the customers predicted to have the k largest data consumption. Leveraging these observations makes optimization possible.

The first possibility is a brute force approach. That is, try every combination of N1, N3, N5, N7, N10 meeting the constraints and return the best one. The current implementation has complexity O(N5), so there may be serious computation issues when N ≈ 1000.

If a faster but less exact algorithm is needed, a hill-climbing algorithm may be appropriate. Hill climbing is the discrete version of gradient descent. It works by computing taking steps in directions where C improves. It terminates when all of the surrounding values have higher values of C. While the minimization problem likely has a unique optimum, hill-climbing does not necessarily find this optimum, although preliminary tests show that is comes close.

Run-time comparison: For N = 100 customers with consumption levels drawn from the Poisson distribution with λ = 5, the brute force algorithm required 5.5 minutes while hill-climbing required 0.06 seconds. For comparison of accuracy, the minimum of C was 3203 and hill-climbing found 3206.

### Community Phone is Hiring

Was this interesting to you? We are hiring a full stack software engineer to help us write software in the older telecommunications industry. If you are interested, please email james@[insert the domain on this page] to learn more.

## Leave a comment: