Solving a linear optimization problem on incentive allocation | Hacker News Reader

Solving a linear optimization problem on incentive allocation

eng.lyft.com

115 pointsmgrover22 comments

It's not the most accessible, but it's pretty interesting. Turning a problem into its dual has always been a bit of a dark art to me, but this article makes the benefits of doing so reasonably clear.

Turning a problem into a dual version is mostly a mechanical thing—you can immediately write it down in the case of LPs, for example[0], and many other convex cases [1].

——

[0] https://en.m.wikipedia.org/wiki/Dual_linear_program

[1] http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf slide 23 on down.

The procedure is mechanical, but understanding why it works is quite a bit harder.

Oh sure, I agree with that. For more context, I highly recommend chapter 5 in B&V.[0]

——

[0] http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page229

I really recommend Tim Roughgarden's notes for understanding duality!

* L7 (Intro): http://timroughgarden.org/w16/l/l7.pdf

* L8 (Duality I): http://timroughgarden.org/w16/l/l8.pdf

* L9 (Duality II: http://timroughgarden.org/w16/l/l9.pdf

Not very interesting. You see allocation problems solved all of the time in finance, and this blog post doesn't have anything new.

I also doubt that it's optimal. An implementation using Hierarchical Risk Parity for instance would be more interesting. I assume you can model risk/uncertainty here.

By the way, Google has an OR tools framework that implements these kind of solvers for you:

https://developers.google.com/optimization

Uninteresting comment. You see critical, speculative comments that offer no technical insight on Hacker News all the time. I also doubt the article was read. Demonstrating actual effort and understanding would be more interesting.

What kind of insight did you want? Simply Google "portfolio optimization" and you will find many more interesting techniques.

This is a basic LP problem that you'll come across in a textbook.

How many HN readers read about OR before? Haven't read the blog post yet but it seems like a nice way to refresh my knowledge from some obscure lecture I attended about it ~5 years ago ;)

Here's an interesting comment with an interesting reply: https://news.ycombinator.com/item?id=21336687

By contrast, you effectively said, "Heh, I've seen fancier models. BTW, you can just plug your stuff into Google."

BTW, you can just plug your stuff into Google

Well, yeah, for something so rudimentary. Use a library. Nothing to see here.

I think you are probably right, this does not seem optimal, it doesn't even seem that they recognized the class of problem that this is? It seems like they are attempting to use a greedy algorithm on a problem which very obviously has local extrema.

It seems like they are attempting to use a greedy algorithm on a problem which very obviously has local extrema.

Yep. You'll end up with a lopsided allocation, with one or two allocations holding a very large percentage of the total allocation.

Distributing the allocation weights could help, e.g. with ensembling, regularization or some other kind of penalty.

Are there recommended resource for understanding and applying these type of problems? I am quite interested in optimization and its real life application, currently reading linear optimization by bertsekas

Take a course on discrete optimization. There's one on Coursera.

Convex optimization is also useful if you care about optimizing convex functions. Which I bet you do.

There's also COIN-OR:

https://www.coin-or.org/

When i compared them a year or so ago, my conclusion that OR-Tools had more focus on engineering, making the whole thing easy to integrate etc, whilst COIN-OR had more sophisticated solvers, and gave you lots and lots of knobs to tweak.

Isn't this a textbook assignment problem? https://en.wikipedia.org/wiki/Assignment_problem

Knapsack version https://en.wikipedia.org/wiki/Knapsack_problem#Definition where "coupons" are items with costs and values.

yeah, this problem is precisely the multiple-choice knapsack problem.

Since their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.

Given there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition.

1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.

I thought you were right but actually no, you'd need more assumptions. Consider this example:

Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, value 3.99.

Type B: coupon b1 has cost 1, value 1.

We have 100 people of Type A and 100 people of Type B. The total budget is 200.

The optimal solution is to pick all Type A people, coupon a2, for a value of 399.

Greedy picks all Type A people, coupon a1, and then all Type B people, coupon b1, for a value of 300.

Reply on news.ycombinator.com