# Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan.

Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some amount of data that is included (i.e. 1000 mb). Hotspots that share the same rate plan can "pool" their data allowances, so if there are 5 hotspots on the 1000mb plan, their pool is 5000mb.

Typically the cost of using more than 1000 mb (overage) is prohibitive. Similarly, using less than the pool (breakage) means you're paying for data which you did not use.

What approach can I use to find the optimal assignment of rate plan to hotspot such that the overage and breakage of each rate plan's pool is minimized?

We've tried some simple methods based on sorting the list by data usage and then "filling" the pools from the bottom up, switching to a higher pool when needed. We've also done this from top down, and by selecting midpoints in the list and expanding out.

The issue with these approaches is that we're able to improve the solution they output by cherry picking a few hotspots to move around. We're struggling to codify the heuristics we use to "cherry pick" the hotspots because we're quite new to this type of a problem.

I've looked into the bin packing problem, but we're unable to reconcile ours with it since our bins can expand or contract based on how many hotspots are in each.

EDIT 2:

We can assign the rate plan for a hotspot for a given month at any time during that month. However practically this operation takes some time, and to be safe we want to do it at least 12, but preferably 24 hours before the end of the month. This gives us time to redo the assignment if something fails, and to check our work. Additionally it takes at least another 24 hours to get the data from the Hotspots about their usage, so in practice we need to do the assignment about 48 hours before the end of the month. Because of this we make a short term prediction (linear) of what the Hotspot will do in the last 5-10% of the time it has in the month.

The list of rate plans is finite (there are usually 5, but in some countries we have only 3 or as many as 10). The rate plans do have different prices that tend to become cheaper on a per MB basis when more data is included. Assuming the rate is fully utilized, 1 MB on the 5000MB rate is less expensive than 1MB on the 500 MB plan, so we prefer to use the larger rate plans. However the difference in price per MB is not that large, so we've decided to assume all rates are equally price efficient to simplify the problem. We may refine further once we figure out how to optimally fill up the pools.

Here is a illustrative example of the rate plans:

+--------------+---------------+--------------+
| rate_plan_id | included_data | monthly_cost |
+--------------+---------------+--------------+
| R1           | 5000MB        | $200 | | R2 | 3000MB |$125         |
| R3           | 1000MB        | $45 | | R4 | 500MB |$24          |
| R5           | 200MB         | \$12          |
+--------------+---------------+--------------+


Here is a illustrative example of the data from the hotspots:

+---------------+---------------------+--------------------+
| serial_number | last_updated_at     | data_used_in_month |
+---------------+---------------------+--------------------+
| 00001         | 7/21/2014 9:12:12Z  | 7612MB             |
| 00002         | 7/21/2014 9:12:14Z  | 122MB              |
| 00003         | 7/20/2014 14:01:52Z | 463MB              |
+---------------+---------------------+--------------------+


We have not looked into bipartite matching problems yet. We are doing that now, thanks for the suggestion. We're also looking at BNB and Bin Packing, but we're new to the field so any tips or potential solutions you have would be much appreciated.

UPDATE:

We built a branch and bound algorithm to try and solve this which I've pasted below. This algo works by starting at the hotspot with the most data use, then testing all available rate plans (sorted ascending by amount of pooled data included) left to right to see if they exceed overage limits (default is no overage allowed) or if they create breakage (default is 5% breakage allowed). If limits are exceeded it moves to the right (next highest rate) and tests again. If no limits are exceeded it writes this rate plan to the "working branch" and moves down to the next smallest node repeating the above. If it reaches the right most (highest) rate plan and limits are still exceeded, it moves "up" the tree, erasing the working branch until it finds a node where it can move right again.

If the algo reaches the last node and no limits are exceeded it writes the working branch to an array and moves up to try and find other solutions. The algo ends when it runs out of branches to test (ie it gets to the first node and tries to "move up".

I think this code is close, but I can't quite get it to work. It either never finds a solution or seems to stall about halfway down the tree.

Could really use some help improving it:

class PoolFillOptimizer

attr_accessor :solutions

def initialize( records, rate_plans, breakage = 0.05, overage = 0.00 )
@records        = records.order(local_total: :desc).pluck(:local_total)
@rate_plans     = rate_plans.order(:pooled_data)

@current_node   = @records.first
@current_rate   = @rate_plans.first

@breakage_limit = breakage
@overage_limit  = overage

@working_branch = []
@solutions      = []

@lowest_branch  = @records.first
end

def solve_tree
catch( :solved ) do
loop do
if not exceeds_limits?
move_down
elsif can_move_right?
move_right
else
move_up
end
end
end
end

private

def move_down
write_to_working_branch

if @records.last == @current_node
save_branch
move_up
else
@current_node = next_node
@current_rate = @rate_plans.first
end

end

def move_right
@current_rate = @rate_plans[@rate_plans.index(@current_rate) + 1]
end

def move_up
backtrack_on_working_branch
throw( :solved, @solutions ) unless can_move_right?
move_right
end

def save_branch
@solutions << @records.zip(@working_branch)
puts "solution found in #{Time.now - @start_time} seconds.  #{@solutions.count} solutions found so far."
end

def can_move_right?
@current_rate != @rate_plans.last
end

def write_to_working_branch
if @lowest_branch > @current_node
@lowest_branch = @current_node
puts "#{@lowest_branch}"
end
@working_branch << @current_rate
end

def backtrack_on_working_branch
loop do
@current_rate = @working_branch.last
@current_node = previous_node
@working_branch.pop
break unless @current_rate == @rate_plans.last
end
end

def previous_node
@records[@records.index(@current_node) - 1]
end

def next_node
@records[@records.index(@current_node) + 1]
end

def exceeds_limits?
exceeds_breakage_limit? || exceeds_overage_limit?
end

def exceeds_breakage_limit?
( @current_node * ( 1 + @breakage_limit ) ) < @current_rate.pooled_data
end

def exceeds_overage_limit?
@current_node > ( potential_pool_space * ( 1 + @overage_limit ) )
end

def potential_pool_space
end

@working_branch.each_with_index.inject(0) do |space_taken, (rate, index)|
space_taken += @current_rate == rate ? @records[index] - @current_rate.pooled_data : 0
end
end

def max_pool_space_possible_from_unassigned_nodes
remaining_candidates_for_pool = @records[@records.index(@current_node)..-1].select{ |x| x < @current_rate.pooled_data }
remaining_candidates_for_pool.count * @current_rate.pooled_data - remaining_candidates_for_pool.sum
end

end

• This sounds like a very simple, contrived, linear optimization problem. What have you tried and where did you get stuck? – Wandering Logic Aug 27 '14 at 0:51
• Alternatively, if linear optimization methods don't work, techniques for bin packing might be applicable. I agree with WanderingLogic: what have you tried? Where did you get stuck? We expect you to make a serious effort before asking, and to show us in the question what you've tried. – D.W. Aug 27 '14 at 1:13
• Also, what are the inputs to the algorithm? What do you know about each hotspot? Are you given the predicted data usage for each hotspot? Are you given a list of allowable plans? Have you tried formulating this as a bipartite matching problem? Construct a bipartite graph, where each vertex on the left is a hotspot, and each vertex on the right is a rate plan; now you want a matching, that minimizes a certain cost function -- have you tried formulating it this way to see if it leads to anything tractable? – D.W. Aug 27 '14 at 4:39
• After the edits it now sounds much more interesting. Do you get to assign the rate plans after you actually know the usage, or are you working with predicted usages for next month? (If the latter then the quality of the answer may be more dependent on the quality of the predictions than on the optimality of the proposed assignment.) – Wandering Logic Aug 27 '14 at 11:45
• Updated with the customized bnb algorithm we've developed - I think it's nearly there, but can't quite get it to work. – l85m Aug 30 '14 at 1:02