Optimization Problem: Recommending Service Providers to Clients

Question

I am new to optimization, not sure if the problem described below is trivial. Any guidance on solution or nudge in the right direction would be very helpful.

Problem:

There are two groups – clients and service providers. Let’s represent clients as $u=1,2,\cdots,n$ and service providers as $v=1,2,\cdots,m$ where $n > m$. The task is to recommend each client the top 3 service-providers based on the propensity score $P$ (which is an $n\times m$ matrix).

The propensity score $p_{ij}$ denotes the propensity of a the client $u_i$ accepting a service provider $v_j$. Ideally, we want to recommend top 3 service providers to a client which have the highest propensity of acceptance. Each service provider has a capacity constraint such that number of clients recommended for one service-provider should be between a certain fixed range: $|\mu^{-1}(v)|\le q_v\,\forall v$ where $\mu$ is the assignment and $q_v$ is the limit to number of assignments for the $v$th service provider.

The solution needs to be practically feasible. We are dealing with few millions clients and few thousands service provider.

I also want to make sure the recommendations don’t change drastically. If propensity scores don't change over time, then we should be recommending more or less same service providers to the same client. If possible, there could be some variation although – say, changing one of the top 3 service providers every now and then will not be a terrible idea.

What kind of techniques are usually used to solve such problems – After doing a bit of research, I found there are techniques such as Linear Programing, Bipartite Graphs to handle similar problems. But I can’t wrap my head around the best course of solution that should be employed in this case.

Answer 1

First, let's split this into two separate problems: making the initial assignments; and updating assignments over time. (If you already have assignments in place, you may only need the second problem.)

The initial problem can be modeled a generalized assignment problem (GAP). Technically this is an integer linear program, with a zero-one variable for each combination of client and service provider, which is unworkable at your dimensions. So we're going to need to do some approximating and settle for a "good" but not provably optimal solution.

I would first look at whether it is possible to assign users to clusters such that the propensity scores for all users in the cluster and any provider are close enough to each other that you would be willing to assign an "average" propensity to all users in the cluster. That would bring the number of variables down from $n\cdot m$ to $n_c \cdot m$, where $n_c$ is the (hopefully small) number of clusters. Now solve a linear programming relaxation of the GAP to get the approximate number of clients in each cluster assigned to each provider, then make those assignments (say, by solving an actual GAP for each cluster, involving only the clients in that cluster and the providers who had a nonzero volume of assignments from that cluster in the LP), with some rounding and finessing to deal with any residual fractions.

If clustering based on propensities is not possible, I would look at whether the full problem can be adequately approximated by a bunch of smaller problems, where each client and each provider exists in exactly one of the smaller problems. For instance, it might make sense to partition based on geography.

Assuming you find a workable idea among those, to deal with updates over time I would use the same approach, adding or removing clients and providers if either group changes over time, and fixing most of the assignments of clients carried over to providers carried over. This leaves a smaller problem in which new clients are assigned, clients whose providers disappeared are reassigned, and possibly some other clients are reassigned to make the overall result better. You can either leave the objective as-is and assume the solver will not reassign an existing client unless there is overall benefit, or you can add a penalty for reassigning clients to discourage it being done with significant overall benefit. (How to decided which assignments are locked and which are allowed to change is left to the reader as an exercise.) The locked assignments turn into adjustments in cluster size or number of clients and capacities of volunteers, and don't directly contribute to the size of the problem being solved.