I have a complex math/combination problem I am trying to solve. I am having difficulty summarizing the problem in mathematic notation and determining whether its fundamentally solvable or not. I would like to ask for some input and introductions to relevant math topics that will help me understand the nature of the problem and how to tackle it.
The problem: There are 10 cell phones on a single account. Each phone uses a different amount of SMS messages and data per month, somewhere between 0 and infinity. Example: Phone 1 uses 13 SMS and 2MB of data, Phone 2 uses 3 SMS and 15MB of data, etc
There are 5 different rate plans I can put each cell phone on. Each rate plan has a price-per-device, a maximum SMS use, and a maximum data use.
Example: Plan A price-per-sim = 1.20USD, max SMS use=20, maximum data use=2MB Plan B price-per-sim = 3.25USD, maximum SMS use = 150, maximum data use = 10MB
Each rate plan "pools" the maximum SMS use and maximum data use between all lines within each plan. If the plan's total SMS use is over its pooled SMS use, the extra is charged at 0.05USD/SMS. If the plan's total data use is over its pooled data use, the extra is charged at 0.35USD/MB
Example: 3 phones are on plan A use a total of 75 SMS and 10MB of data. Service charge = 3 * $1.2 = 3.60USD, Pooled SMS = 3 * 20 = 60, overage = 75-60=15 SMS * 0.05USD = $.75 overage, Pooled data = 3 * 2MB = 6MB, overage = 10MB - 6MB = 4MB * $.35 = $1.40 overage Total plan A cost = 3.60USD + 0.75USD + 1.40USD = 5.75USD Total cost of the account would be that same process for all the rate plans.
I can make the change right up until the last day of the month, and whatever plan the phone is on at the end of the month will be used to calculate that month's use/overage. So my ultimate question is "What plan should each phone be on that will give me the lowest total account bill?"
The equation for computing the overall bill is easy, but how can I represent "for every phone on the account, look up the rate plan and do this computation". Also, is there a way to compute the absolute minimum for this problem separate from computing every possible combination of phone and rate plan?
Edit: Sample data
Phone 1: {"sms": 44.0355, "data": 27.23706},
Phone 2: {"sms": 62.1215, "data": 5.1101},
Phone 3: {"sms": 48.9895, "data": 1.28353},
Phone 4: {"sms": 29.09, "data": 0.6727906},
Phone 5: {"sms": 4.895, "data": 0.1657593},
Phone 6: {"sms": 0.0, "data": 0.0}
Plan 1:{'price':0,'datapool':0,'smspool':0},
Plan 2:{'price':1.05,'datapool':6,'smspool':25},
Plan 3:{'price':3.65,'datapool':6,'smspool':65},
Plan 4:{'price':5.1,'datapool':6,'smspool':100}
You can solve the problem via mixed integer linear programming as follows. For phone $i$, let $s_i$ and $d_i$ be the SMS usage and data usage, respectively. For plan $j$, let $p_j$, $u_j$, and $v_j$ be the price per device, SMS capacity, and data capacity, respectively. Let binary decision variable $x_{ij}$ indicate whether phone $i$ is assigned to plan $j$. Let nonnegative decision variables $y_j$ and $z_j$ be the SMS overage and data overage, respectively, for phones assigned to plan $j$. The problem is to minimize the total cost $$\sum_{i,j} p_j x_{ij} + \sum_j (0.05 y_j + 0.35 z_j)$$ subject to linear constraints \begin{align} \sum_j x_{ij} &= 1 &&\text{for all $i$} \tag1\label1\\ \sum_j (s_i - u_j) x_{ij} &\le y_j &&\text{for all $j$} \tag2\label2\\ \sum_j (d_i - v_j) x_{ij} &\le z_j &&\text{for all $j$} \tag3\label3 \end{align} Constraint \eqref{1} assigns each phone to exactly one plan. Constraint \eqref{2} forces $y_j = \max\left(\sum_j (s_i - u_j) x_{ij}, 0\right)$ to be the SMS overage. Constraint \eqref{3} forces $z_j = \max\left(\sum_j (d_i - v_j) x_{ij}, 0\right)$ to be the data overage.
This approach will find an optimal solution and should perform much better than brute force.