The Optimal Playlist

One of the problems with neighborhoods in parts of Connecticut is the lack of sidewalks coupled with crazy drivers (probably from a neighboring state to its left). To avoid getting run-over, I decided it is safer to do my walking on the treadmill. I'm now getting all the exercise a creaky researcher needs, but I'm not getting anywhere. To overcome this monotony, I hooked up my old iPod-classic for company, but it's time-consuming to generate my preferred playlist : start off with some up-temp music for motivation, then switch to cruise mode, and tone down after my 30/60 minutes of walking.

In India, we have the concept of 'Rasa', a Sanskrit untranslatable that very roughly speaking, includes notions of experiencing certain emotion(s), themes, ambiance, genre, etc. So the sequence of Rasas  matters a great deal. Furthermore, I like to listen to complete songs and hate to end a virtuoso Carnatic performance half way when the exercise session-clock runs out. Furthermore, there are so many languages in India and many have their own pop-culture, folk, and classical genres in instrumental as well as vocal modes, and I prefer a diverse sampling of these to feel more at home.

Putting all this together to achieve an optimized playlist requires a constraint-programming approach. If I also want to optimize a certain objective (e.g., stay close to 12 songs), this turns into an exercise of solving an associated discrete decision optimization problem that can be stated as follows:

Find (preferably) 12 complete non-repetitive songs in a preferred sequence that lasts (almost) exactly 60 minutes, and includes at least n(i) songs having user-specified attribute (i), i = 1, .., n.

If we restate the attribute requirement as a soft-constraint by creating a score-table for including any attribute (e.g. 10 points for including a song with attribute i once,  15 points for two songs with attribute (i), 17 if three or more times) as opposed to the 'must satisfy' version stated earlier, then the playlist optimization problem can be posed as a attribute score-maximizing multiple-choice knapsack problem with a cardinality constraint, followed by a sequencing step. Even with a huge home music database, practical instances of the latter formulation may be relatively easy to solve via combinatorial methods (iPhone app?) and may not require expensive MIP solvers. Then, as a second step, we can sort the included songs into another preference-score maximizing sequence to generate the final playlist, unless of course the sequencing requirements are not that simple (in which case, a more sophisticated optimization approach may be required).


Such an optimized playlist is also useful if you want to build an auto-pilot DJ for your next house party. If your approach can solve this problem on-demand, you would also be able to dynamically re-optimize the playlist after manual intervention.

It seems apt to terminate this post with a Carnatic-Western classical fusion piece.



Updated on March 30: The objective function above is deterministic so there is a good chance that the you will get the same set of songs to listen to each day, which is not very useful. To introduce diversity and exploit the fact that in practice you tend to get several alternative optimal solutions to such problems, add a small amount of clock-dependent noise to the attribute-score and sequence-preference score. This will likely do the trick.