Solving a linear optimization problem on incentive allocation
How to solve a linear optimization problem on incentive allocation?
By David Shmoys and Shujing WangAt Lyft, scientists solve all kinds of optimization problems. While solvers can come in handy, there are times when complicated or large-scale problems can be simplified and solved with customized and efficient algorithms. In this post, we will show how to use linear programming duality to transform and solve an incentive allocation problem.A hypothetical example of an incentive allocation problem: Given an eligible group of riders or drivers, a set of incentives and a budget, we want to allocate the incentives to the riders or drivers to maximize incremental metrics such as rides or driving hours.Incentive allocation is a common theme at Lyft. For example, we send riders promotional coupons and send drivers bonuses, in the hope of optimizing objective functions such as maximizing incremental rides or driving hours. In this context, the main constraints are (1) a total budget constraint on how much we can spend on the incentives, and sometimes (2) a requirement that each rider or driver can be only given at most one incentive. Such allocation problems can be easily formulated as integer programming problems, which can be further relaxed to be linear. Although such problems have simple structures, their problem size can easily grow large (e.g. there can be many incentives, or a large population of riders). So we wonder: is there a fast and efficient way to solve this problem that can out-perform open-source solvers? The answer is yes. In this particular use case, we develop an algorithmic idea based on duality.Problem FormulationFor simplicity, let us consider a scenario of giving out coupons to riders. We define the following:We can then formulate the problem with a linear programming relaxation (P) as follows, where the integrality constraint of the variables is omitted. We know that we are going to get at most one variable with a fractional solution (nice property of LP) in this relaxation, which is acceptable in exchange for the efficiency of solving this problem:Here, we have preprocessed the data so that we may assumeCoupons eliminated in the preprocessing step are dominated by at least one coupon in the feasible set. In other words, the cost, value and efficiency of feasible coupons for each given rider are in increasing order. We leave the mathematical proof to interested readers (the idea is that if this relationship is violated, there is always a feasible perturbation in the optimal solution for which you can make the solution even better, leading to a contradiction).From the primal to the dualTo solve the linear programming relaxation, we will first solve its linear programming dual. We define the following dual variables:Then the dual (D) is as follows:Let D(λ) denote the dual linear program (D) for a fixed value of λ ≥ 0. In considering this LP, note that the optimization problems for each rider i = 1, . . . , m, is an independent (trivial) problem: we simply setand hence the optimal value to D(λ) isWe denote this expression as (E) for the rest of the post.to solve (D), we simply need to find λ that minimizes this expression (E).Solving the dual LPWe show how the compact form of the dual given as finding λ to minimize (E) provides a direct way to solve this LP. For now, focus on one rider i and the corresponding term in (E). We observe the following:Therefore, we want to create a list of breakpoints for rider i by checking each of the intersections of of the kᵢ lines, starting with the intersection of j=1 and j=2. The key point here is that we only keep breakpoints that are monotonically decreasing. After this process, we may assume without loss of generality that each rider i, who is now left with gᵢ (gᵢ ≤kᵢ) incentives, has a list of eligible coupons and breakpoints that satisfyThe figure below provides a graphical explanation, and we leave the mathematical proof to interested readers.Here is a graphical illustration of the elimination and breakpoint creation step. Given a rider i who starts with 4 eligible coupons indexed by 1, 2, 3 and 4, we first draw the lines vij — λcij (j = 1, 2, 3, 4) to construct the function yi(λ). Coupon 2 is then eliminated because its line does not contribute to the frontier of yi(λ), which means that the constraint corresponding to it is never tight at optimality , i.e. coupon 2 will never be chosen. We are left with coupons 1, 3, and 4 in our eligible set, and we reindex them to be coupons 1, 2 and 3 for simplicity. We have three breakpoints λi1, λi2 and λi3, where coupon 1 is chosen for in λ in [ λi2, λi1], coupon 2 is chosen for in λ in [ λi3, λi2] and coupon 3 is chosen for in λ in [ 0, λi3]. In this example, ki =4 and gi = 3 after the elimination process.Now consider what we have learned about the objective function (E). For a fixed rider i, the corresponding term in the summation gives rise to a piecewise linear function with the gᵢ breakpoints. Hence, in considering the sum in (E), we again get a piecewise linear function with the union of these breakpoint values (over all choices of i) as the resulting breakpoints. Let 0 = ρ₀ < ρ₁ < ··· < ρn be the union of these breakpoints. Between any pair of breakpoints, the function D(λ) is an affine function (i.e., it is of the form αλ + β); furthermore, D(λ) is convex with the slopes in these pieces are an increasing function of λ. For λ sufficiently large (bigger than ρn), the slope is clearly C; at λ = 0, the slope iswhich we can assume is negative. Otherwise, we would simply assign each rider their maximum value coupon (which is also their maximum cost coupon), since that does not exhaust the budget, and hence is clearly optimal. In all other cases, there is a breakpoint ρ* for which the slope for λ < ρ* is negative, and for λ > ρ* is positive. In that case, D(λ) is minimized when λ = ρ*.The Dual LP optimization algorithmAt a high level, the algorithm to compute the optimal dual LP solution works as follows: maintain the breakpoints as m sorted lists, and iterate through the entire set of breakpoints in a descending order, computing the current total slope, until the first point at which the slope switches sign. Note that iterating the breakpoints in a descending order makes the algorithm a (relatively simple) extension of the case when selecting the greatest bang/buck choice for each rider exhausts the budget (and is, again, clearly optimal, where each rider except the one that uses the last bit of budget is guaranteed an integral assignment).For each rider we keep a pointer to the largest element in the sorted list of breakpoints that has yet to be processed. We start with an active set of breakpoints, one for each passenger i = 1, . . . , m, initially equal to vᵢ₁/cᵢ₁(which is that passenger’s greatest bang/buck value). We initialize the current slope, which is for λ greater than all breakpoints, equal to C, and introduce the notation that cᵢ₀ = 0, i = 1, . . . , m, for a latter use (though this doesn’t correspond to any coupon option).We keep the currently active breakpoints in a priority queue, and in each iteration, extract the maximum remaining one. Suppose that the current breakpoint extracted corresponds to coupon j* for rider i*. We know the slope of the dual objective function greater than this breakpoint, and want to compute the slope just less than it. To do so, we need to reflect the change from the old contribution to the slope for i* to its new one: the new one is option j*, and the old one is option j* − 1. If we let let OLD denote the cost of coupon j* − 1 for rider i* and let NEW denote the cost of coupon j* for rider i*, then the change of cost is OLD-NEW. To replace the breakpoint extracted for i*, we insert the next breakpoint of i* into the priority queue (if there is one available), and the algorithm continues to the next iteration. We continue to iterate until we have decreased the slope from C to below zero.It is possible that multiple riders could have the same “next” breakpoint, in which case we extract the next maximum in an arbitrary order. We update the slope after each extraction in the same way, and possibly we will have reached the termination point (because the sign becomes negative) after processing some of these common values, but not others. This will give rise to multiple optimal solutions for the primal LP.From optimal dual to optimal primal LP solutionWe now have obtained the optimal dual solution. We have already assumed that the slope of D(λ) at λ = 0 is negative, and hence λ* > 0. To compute the optimal primal solution, we take advantage of the complementary slackness conditions for primal and dual LP optima, which gives us the following:The case in which each breakpoint corresponds to a distinct unique rider is easy to understand. In this case, the optimal value λ* for (D) is the breakpoint corresponding to exactly one rider i*, and is between breakpoints for every other rider. Thus, for all other riders other than rider i*, there is a unique maximum j(i) attained in the term corresponding to i in the sum (E); hence, the corresponding option must be set equal to 1 for that rider. This argument can be extended to the case when the optimal breakpoint corresponds to multiple riders.The correctness of the algorithm follows directly from showing this pair of primal and dual linear programming solutions are both feasible for their respective optimization problem, and satisfy the complementary slackness conditions.Summary of the algorithmRecall that the algorithm produces a fractional solution in which at most one passenger is not given an integral assignment. In the algorithm below, we assign the more expensive coupon for the rider at the breakpoint and obtain an solution that is just fractionally more valuable than the optimal LP solution. Putting it all together, the pseudo code for solving the dual LP to get the primal coupon allocation looks like the following:ConclusionIn this post, we have described an elegant way of solving a linear optimization problem with a budget constraint. In practice, the speed and efficiency of this tailored algorithm outperforms those of open-source LP solvers more than tenfold. On the flip side, there are obvious limitations (maybe clever extensions?) of the algorithm because of its rigid dependence on the problem structure. Most importantly, by showcasing to you how fundamental knowledge in optimization (without fancy blackbox methods) can help to solve problems we face at Lyft, we hope that you feel inspired to learn more about optimization, and about Lyft!If you enjoyed this post, follow and recommend! To learn more, check out our other Science posts.As always, Lyft is hiring! If you’re passionate about developing state-of-the-art machine learning/optimization models or building the infrastructure that powers them, read more about our Science and Engineering roles and reach out to us.We would like to thank Kedar Thakkar, Lei Ding, Alex Wood-Doughty and Jose Abelenda for their contribution/support to this work. Also, this post would not have been possible without the help of Matt Izant, Hao Yi Ong, Mark Grover, Ryan Lane and Alex Rafter. Many thanks!