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].
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.
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:
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.
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 ;)
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.
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
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.
23 comments
[ 3.2 ms ] story [ 78.5 ms ] thread——
[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.
——
[0] http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page229
* 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
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.
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.
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
This is a basic LP problem that you'll come across in a textbook.
By contrast, you effectively said, "Heh, I've seen fancier models. BTW, you can just plug your stuff into Google."
Well, yeah, for something so rudimentary. Use a library. Nothing to see here.
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.
Convex optimization is also useful if you care about optimizing convex functions. Which I bet you do.
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.