Solving a linear optimization problem on incentive allocation • Hacker News Board

Re: Solving a linear optimization problem on incentive allocation

#21

Post by bo1024 » Wed, Oct 23, 2019, 8:55 PM UTC

greedyalgo wrote: post #7

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.

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.

Re: Solving a linear optimization problem on incentive allocation

#22

Post by twic » Wed, Oct 23, 2019, 9:13 PM UTC

codesushi42 wrote: post #9

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/…

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.

Re: Solving a linear optimization problem on incentive allocation

#23

Post by chaoxu » Wed, Oct 23, 2019, 9:38 PM UTC

jvanderbot wrote: post #20

ltbarcly3 wrote: post #6

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.

Re: Solving a linear optimization problem on incentive allocation

#24

Post by codesushi42 » Wed, Oct 23, 2019, 9:58 PM UTC

1000units wrote: post #14

codesushi42 wrote: post #11

Earlier quoted context omitted.

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.

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.