The Birchbox Problem

At Birchbox one of our fundamental aims is to help our customers discover products and brands they will love. The most visible way we do this is via the Birchbox that we send to our subscribers each month.

Suppose that in a particular month we have N subscribers to whom we need to send a Birchbox, and we have M products that we can put into their boxes, with quantity q_i of product i. The Birchbox Problem is the assignment of products to subscribers such that we maximize happiness. It can be expressed mathematically as

\max_{\textbf{B}} \sum_{i=1}^M \sum_{j=1}^N H(i,j) \textbf{B}(i,j) + F(\textbf{B})

such that

\forall i: \sum_{j=1}^N \textbf{B}(i,j) \le q_i


\forall j: \sum_{i=1}^M~\textbf{B}(i,j) = n,~\forall i,j: \textbf{B}(i,j) \ge 0.

The assignments are captured in \textbf{B}, a binary assignment matrix, i.e. \textbf{B}(i,j)=1 if product i is assigned to user j.

Happiness can be a difficult notion to define, but there are various proxies that we use to quantify it. Some are explicit, for example, we track how much customers like certain products via star ratings. We also look at implicit signals, including which people buy the products they receive in their boxes (conversion); changes in subscription status (cancellations, upgrades); and friend referrals.

To best assign products to subscribers, we require a predictive model that can gauge how each subscriber will like each product and their box as a whole. In the optimization problem above, the function H(i,j) is our predictive estimate of user j‘s satisfaction with product i and therefore the first term in the objective function captures the additive happiness attained by assigning product i to user j.

The second term in the objective, F(\textbf{B}), is used to assess the quality of the assignment at a higher level. For example, F can be used to express that certain products must be paired together (e.g a shampoo and conditioner), or even that the total number of “types” of boxes should be bounded.

The first constraint in the optimization problem expresses that we have at most q_i of product i, and so this is the most that we can assign. The final pair of constraints express the fact that every user needs to be assigned n products. (In reality n \in \{4,5,6\} and varies from box-type to box-type in a manner controlled with F.)

The problem above can be recognized as a combinatorial optimization problem. The choice of happiness functions and other variables affect the difficulty in solving this problem, but with most reasonable choices, the problem is NP-Complete. Fortunately however, that doesn’t mean we can’t tackle the problem in practice!

In future posts we will discuss how we go about formulating and solving the Birchbox Problem in more detail.