Re:Solving a linear optimization problem on incentive alloca...
by s_Hogg on Wednesday October 23, 2019 @06:52AM
(#21333264)
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.
Re:Solving a linear optimization problem on incentive alloca...
by LolWolf on Wednesday October 23, 2019 @12:13PM
(#21336071)
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].
Re:Solving a linear optimization problem on incentive alloca...
by codesushi42 on Wednesday October 23, 2019 @02:09PM
(#21337223)
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:
Re:Solving a linear optimization problem on incentive alloca...
by ltbarcly3 on Wednesday October 23, 2019 @02:22PM
(#21337335)
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.
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.
Re:Solving a linear optimization problem on incentive alloca...
by bulldoa on Wednesday October 23, 2019 @02:24PM
(#21337355)
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
Re:Solving a linear optimization problem on incentive alloca...
by 1000units on Wednesday October 23, 2019 @02:13PM
(#21337257)
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.
Re:Solving a linear optimization problem on incentive alloca...
by marktani on Wednesday October 23, 2019 @02:22PM
(#21337336)
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 ;)
Re:Solving a linear optimization problem on incentive alloca...
by greedyalgo on Wednesday October 23, 2019 @01:13PM
(#21336687)
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.
* 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
——
[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
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
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.
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.
Convex optimization is also useful if you care about optimizing convex functions. Which I bet you do.
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.
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.
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.