0

Suppose I have some mobile phones that use some amount of data each month. There are 3 rate plans, each with a capacity and a monthly cost:

  • 5MB, \$1 per device per month
  • 25MB, \$4
  • 50MB, \$7

The plans are "pooled" such that each device on a plan increases the capacity of that plan: i.e. a 5MB plan with 10 devices on it has a capacity of 50MB. An individual device does not have its own limit (a 5MB plan device can use more than 5MB/month), but the plan it's in does.

The goal is to optimize for minimum cost.

My question is: does this problem already have a name, or considered a particular knapsack/bin-packing variant?

T3db0t
  • 105
  • 5
  • 1
    The solution is trivial: buy 50MB packages until you're within 50MB of your requirement, then one 25MB package if you're not within 15MB of your requirement already, then between zero and three 5MB packages to get past your target, as required. [There's an equal-cost solution where you buy the 25MB package if you're not within 20MB, then between zero and four 5MB packages, but this version gives more headroom for the same cost). – user3482749 Jan 14 '19 at 22:48
  • @user3482749 Thank you! Yes, I know the solution—I'm just curious if this particular formulation has a name or what problem it would be considered a variant of. More of a change-making problem than bin-packing I guess... – T3db0t Jan 14 '19 at 23:08
  • I doubt it. It's too simple: the solution is always essentially the same. – user3482749 Jan 14 '19 at 23:11
  • @user3482749 OK—what about minor variants where the pools are per-plan or groups of plans? (i.e. not just one big pool) Are the solutions all identical? – T3db0t Jan 15 '19 at 18:30
  • Not quite, but nearly: you do the above on each pool separately. – user3482749 Jan 16 '19 at 00:01
  • @user3482749 I'm not sure that the same solution applies to the case where each plan is its own exclusive pool. Each device on the plan increases the capacity by the plan amount. So if you start stacking devices with low usage into the big plan, its capacity can become so large (and hence expensive) that it will never be filled. The solution I'm using is to start with smallest usage in the lowest rate plan and fill from the bottom up. I don't see how it would work from biggest down. – T3db0t Jan 17 '19 at 16:56
  • Clarification: If you start stacking even very high-usage devices into the biggest plan, you will start increasing the capacity of that plan far, far higher than the entire rest of the usage could ever fill, thereby wasting a ton of "room" and hence money – T3db0t Jan 17 '19 at 17:47
  • Here's a full explanation: https://math.stackexchange.com/questions/1886405/optimizing-data-usage-among-pooled-rate-plans – T3db0t Jan 17 '19 at 18:08

1 Answers1

1

It's a pretty simple mixed integer programming formulation.

$$\begin{align*} \min \quad&\sum_{i}\sum_{j} x_{i,j}c_j\\ \text{s.t.}\quad&\sum_{i} d_{i}x_{i,j}\leq \sum_{i} x_{i,j}D_j\\ &\sum_{i}x_{i,j}=1\\ &x_{i,j}\in\{0,1\} \end{align*}$$ where

  • $x_{i,j}$ denotes whether cellphone $i$ is on plan $j$,
  • $c_j$ is the cost of plan $j$ per device,
  • $d_i$ is the data usage of cellphone $i$, and
  • $D_j$ is the data per device for plan $j$.

I'd consider this to be a variation on the generalized assignment problem.

nathan.j.mcdougall
  • 1,854
  • 16
  • 22
  • Fantastic, this is exactly what I was looking for. I'm a programmer trying to learn the mathematical modeling better; how can these expressions be used to actually arrive at the $x_{ij}$s? Similarly, how would one use the expressions to, say, prove equivalency with some other algorithm? (Hopefully these questions are not nonsense) – T3db0t Jan 17 '19 at 19:16
  • These problems are generally NP-hard (the actual generalized assignment problem is NP-hard). You will need to use mixed integer programming solving software to get an answer for all but the simplest problems.

    For example, in python there is PuLP, for Julia there is JuMP.

    It's not exactly clear to me what you mean by 'equivalence', but you can certainly show that this problem is a more general case or a more specific case of another problem, and conclude things about it from that.

     – nathan.j.mcdougall Jan 17 '19 at 19:28
  • Gotcha—thank you. I have done some constraint logic programming so this is very interesting! – T3db0t Jan 17 '19 at 20:28