What kind of knapsack/bin-packing problem is this?

Question

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?

Answer 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.