Writing Papers at Startup: My Work at Onera

Last month, Carnegie Mellon's wrote an article about our work at Onera, my previous startup. This was based on our paper that recently was published at MSOM 2022, which was joint work with R. Ravi, my dissertation committee member and Sagnik Das, a PhD student. It is nice that the work that we did at Onera can be memorialized at least in part in this paper, we will go over that in this post.

And the work that I did at BloomReach, the previous startup can be memorialized at least in part in our WWW 2015 paper (also joint work with R. Ravi and his PhD student Arda Antikacioglu). I collect some memorabilia from my work like a serial killer I guess. Here's some more memorabilia that I have from Onera - our first "Welcome to Onera" sign that was printed on A4 paper and stuck on the wall in sequence (attached above) and one of our very first discussions on the theoretical underpinnings of Onera (attached below) that was written in the offices of Bain Capital Ventures below on one of those large post-in poster boards. Both of which I still have in my possession.

I am looking forward to starting to showcase some of the cooler things we are doing at Regie.ai soon as well. Got to collect some of that Regie.ai memorabilia.

Both the WWW 2015 paper and the MSOM 2022 papers had one thing in common. It was kicked off by a cute mathematical theorem. I really enjoy these because it is actually one of those things that are elegant, practical and based on the real-world. I am also glad that I can write a paper once in a while and keep at least a little bit of that brain activity going.

In this post, I wanted to talk about the MSOM 2022 paper here. I realize it may need some math background but I'll try to keep it accessible.

The main problem that we solve in this paper has to do with omni-channel fulfillment - specifically buy online ship from store and buy online pick up in store programs that retailers that running. Basically, they started using stores as fulfillment centers but store inventory is extremely inaccurate. When a store associate goes to 'pick' an item to do fulfillment, on the high side, it succeeds only 60% of them. Yes, that bad. Due to theft, scanning issues, misplacement and a whole bunch of other issues. So how do you not cancel too many buy-online ship from store orders or buy online pick up in store orders when the underlying data is so unreliable while minimizing labor cost, shipping cost and cancellation? That's basically the paper.

Now lets get a bit more formal. Lets say there are J stores of the retailer. Lets say there are L stages of pick attempts - meaning, a store associate tries to find the item in a store for ship-from-store and can not find it, and so reports back to the order management system that routes to a second (among J stores) that may have it in stock and this keeps going until the item is picked or L stage attempts have failed and the order has to be cancelled. Lets say that the pick attempt at a store j fails with probability φ_j. If it is successful (with probability 1 - φ_j), lets assume that the shipping cost is s_j. For each attempt to pick lets say that the labor cost is b_j.

Here's the first cute observation, lets define unreliability factor r_j = s_j + b_j / (1 - φ_j). Then in the optimal way of attempting to fulfill an order, you will always have to attempt it in a non-decreasing order of the unreliability factor r_j. The main idea is how that expression above beautifully captures the relationship between shipping cost s_j, labor cost b_j and pick failure probability φ_j (that eventually is responsible for the order getting cancelled) into one unreliability score for each store.

When I was thinking about this initially it was never clear that such an expression could exist. Immediate thoughts would be that optimizing this would be hard (specifically NP-hard) and its unlikely we'll have any way to get to the right set of stores, but this expression then gave us a lot of confidence that there is one score we can assign that converts what is a multi-dimensional cost to a single dimensional cost.

Now immediate next thought is, great. The problem is very simple, let's arrange the stores in increasing order of the unreliability factor and pick the first L stores. But that actually doesn't work. Counterexample in the paper which involves introducing one more parameter which I am avoiding here for simplicity but the main reason is that it would end up canceling a lot of orders than the optimal solution.

But this leads to a fairly typical dynamic program. First order the stores by unreliability factor. Now we get typical induction / recurrence type dynamic program table. Define W(j', l') to be the optimal selection of j' remaining picks of the l' remaining stores. You can now define

For those familiar with dynamic programs, mostly you just now need to think of the size of the DP table, i.e., all possible values j' and l' can take which is JxL and the work done to fill any entry of the DP table which is J and so can be solved in O(L J^2) time which is very very efficient compared to any exhaustive approach.

Notice that in the above approach we needed to know shipping cost s_j (which you will since it is deterministic based on store location, destination location), the labor cost (which is also deterministic on the labor costs of that store for the associate) and the pick failure probability. The hard part is that the pick failure probability is an estimate. In the above method we assumed that the pick failure probabilities was independent on the stage at which it is picked. That is, if we have tried to find it in 3 stores and failed, the probability of finding it in the fourth store is the same as though you attempted to pick from the fourth store first. In reality there is an underlying reason why picks are failing because of the nature of the item (imagine a fast moving item on sale that customers are picking faster than the store associate). Now the estimate of pick failures φ_j can be extended to be an estimate of pick failures at each level φ_jl where l is the stage of attempting to find the item in store j.

Under this estimate of pick failures as well, we show that you can extend the dynamic program to find an optimal method of selecting stores in O(L! J log L) time which is actually pretty efficient since L is in the range of 3-5 and J the number of stores is really large - often in the hundreds if not thousands.

The paper then goes over the linear programming approaches to solve the fulfillment problem which will look similar to the post-it notes from 2013 above including the network diagram on the paper. The paper then extends to stochastic programming for a more general class of problems and an efficient algorithm using infinitesimal perturbation.

Full paper here

I can't wait to showcase some of our cool work at Regie.ai.