Today's dish is short and sweet: given a number of potential returns associated with certain tasks, and given limited allocable time for multiple people, how can we make sure everyone's time is used to the max for the best global welfare?
Recipe difficulty
- Statistics: 🔥🔥 - you need some basic understanding of common OR problems such as bin-packing and the 0-1 knapsack problem, but nothing crazy
- Technical: 🔥 - no code ability required.
- Time required: 🕜 - very short blog post today as I only had 30 minutes before knapsacking my way to the movies!
What it is
The Knapsack problem is one of the most classical NP-hard questions: we have a knapsack (a backpack) with a capacity C, and Y items with each a weight W and a value V. How do we maximize the value without overshooting the backpack's capacity?
\[ \sum(W) \ s.t. \ \sum(W)\leq C \]
Why is it useful
Moving the problem into a business setting: we have multiple new interns (knapsacks), each with a fixed amount of available hours per day; and we have multiple tasks, each generating a certain revenue but taking up a certain time.
There's a plethora of available algorithms for this, but since I don't have time for this today, let's just use the optimization package Adagio in R.
In just a few lines of code, assuming we have three interns:
install.packages('adagio')
require(adagio)
returns <- c(78, 35, 89, 36, 94, 75, 74, 79, 80, 16)
task_time_minutes <- c(18, 9, 43, 20, 59, 61, 70, 75, 76, 30)
available_minutes <- c(100, 150, 350)
mknapsack(returns, task_time_minutes, available_minutes)$ksack
> 1 1 1 1 2 2 3 3 3 2
The first intern, who has 100 minutes of time, will do the first four tasks. The second intern, with 150 minutes of time, will take up the fifth, sixth and last task; and the third intern does the rest.
No interns were harmed while writing this post and I don't endorse overloading colleagues like poor knapsacks 😄
Note: for Python you can use Google's OR-tools instead of Adagio.
