# Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem.

I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ultimately want to achieve is to identify inventory draws not accounted for by a sales transaction (ie. missing inventory taken). To add to the complexity, a draw can correspond to more than one sale and a sale can correspond to more than one draw (many to many).

Any ideas on how I should start this?

Here is a sample of real data: • Can you provide an example of the type of data? What is the resolution/precision? How much data do you have? Given your problem description, I am not certain you need explicit matching. Perhaps you only want to flag "suspect draws" for closer inspection? (Say look at time series of cumulative draws - sales, and flag draws that are associated with "large & persistent" anomalies.) – GeoMatt22 Oct 9 '15 at 3:22
• Thanks for looking at this GeoMatt22. I have edited my original question to include sample data. I think it's not persistent anomalies I would want to flag. It's any anomalies. The flagging also only needs to be one way (ie. flag the draws that don't belong to a sale). In this sample data, there actually isn't any draw that needs to be flagged. – Kee Lim Oct 10 '15 at 5:36
• Can you also provide the ground truth solution for your example? i.e. What is the expected outcome? – Tolga Birdal Oct 10 '15 at 8:44
• Kee Lim, by "large persistent anomalies" I was thinking if you compute net(t) = sum( sales(i) - draws(i) , i <= t ), then the expectation would be net(t) ~ 0. Of course, there will be minor fluctuations with |net(t)| > 0 over short times. So, "large & persistent" could be something like |moving_average( net )| > tol. – GeoMatt22 Oct 10 '15 at 14:58
• Anyway, from what you have said it seems that your question is essentially "How to detect anomalies?", in which you do not necessarily need to assign explicit correspondences (i.e. solve an assignment/matching problem). Given this, you might get better responses by migrating this question over to Cross Validated. – GeoMatt22 Oct 10 '15 at 19:37

You don't say what is the condition when an inventory draw is allowed to match a sale, but I'm going to assume it is: both the timestamp and the item must match, if we want a particular sale to be matched to a particular inventory draw.

If this is right, your problem is separable by (time,item)-pair: for each timestamp that appears in the dataset and each item, look only at the sales & inventory draws that occur for that timestamp and that item and see if any of the inventory draws can't be matched up to a sale; then move on to the next pair. This breaks down the problem into smaller pieces.

Given your problem statement, the following algorithm is the best you can do, for each (timestamp,item)-pair:

Let $d_1,\dots,d_m$ denote the quantities of the inventory draws (for that (time,item)-pair). Let $s_1,\dots,s_n$ denote the quantities of the sales orders (for that (time,item)-pair). Then:

• If $d_1+\dots + d_m < s_1 + \dots + s_n$, something is wrong with your records (but no inventory draw is suspicious).

• If $d_1+\dots + d_m = s_1 + \dots + s_n$, nothing is suspicious.

• If $d_1+\dots + d_m > s_1 + \dots + s_n$, then at least one of the inventory draws is suspicious. Realistically, there will typically be no way to tell which inventory draw was at fault. More precisely, let $\delta = (d_1+\dots + d_m) - (s_1 + \dots + s_n)$; any subset of draws whose quantities sum to $\delta$ could be suspicious. In other words, for any set $S \subseteq \{1,2,\dots,m\}$ such that $\sum_{i \in S} d_i = \delta$, the set $S$ could be suspicious. You could enumerate all sets $S$, but typically there will be many sets. All you know is that one of those sets is a set of suspicious inventory draws, but you won't know which. Typically, you won't be able to put your finger on any one inventory draw and say that it is definitely problematic or definitely not suspicious (you can only say draw $i$ is definitely problematic if $i$ is present in all sets $S$ such that $\sum_{i \in S} d_i = \delta$; you can only say that draw $i$ is definitely not suspicious if $i$ is not present in any of those sets $S$). Even worse, there will typically be exponentially many possible sets $S$, so finding all of them will probably take intractively long, if you have many orders.

Therefore, realistically, the total quantity of inventory draws for some item at some time exceeds the total quantity of sales for that item at that time, then about all you can say is that at least one of those inventory draws seems suspicious; flag them all for a human to inspect.

To do better than this, you'll need additional information that goes beyond just timestamp, item, and quantity. For instance, you might have additional information, such as the value of the item, the identity of the worker who did the inventory draw, and so on -- that might help you do better.