Re: Solving allocation problems; code review and core.logic

On Fri, Mar 7, 2014 at 3:50 AM, Mark Engelberg wrote: > On Thu, Mar 6, 2014 at 4:56 AM, Laurens Van Houtven <_...@lvh.cc> wrote: > >> Hm. I realize we're unlikely to change the nature of the problem, but >> would it help if we limit the search space? For example, if we only care >> about grants in

Re: Solving allocation problems; code review and core.logic

On Thu, Mar 6, 2014 at 4:56 AM, Laurens Van Houtven <_...@lvh.cc> wrote: > Hm. I realize we're unlikely to change the nature of the problem, but > would it help if we limit the search space? For example, if we only care > about grants in increments of $50 or $100? Instead of working with dollars,

Re: Solving allocation problems; code review and core.logic

On Thursday, March 6, 2014 12:19:25 PM UTC+1, puzzler wrote: > > Even though loco works on this small example, it doesn't scale well for > this kind of problem. I did a test on some randomly generated 3000 people, > and it's slow. (You can set the budget constraint to definitely spend the > wh

Re: Solving allocation problems; code review and core.logic

Even though loco works on this small example, it doesn't scale well for this kind of problem. I did a test on some randomly generated 3000 people, and it's slow. (You can set the budget constraint to definitely spend the whole budget to speed things up, and set a timeout, but the quality of the s

Re: Solving allocation problems; code review and core.logic

On Thu, Mar 6, 2014 at 12:21 AM, Laurens Van Houtven <_...@lvh.cc> wrote: > > Yep. A big part of the issue is that the *real* function that maps grant > fraction to probability of coming is of course unknowable. A linear > approximation is an excellent start. Once I have some test data I'll be > a

Re: Solving allocation problems; code review and core.logic

Hi everyone, On Thursday, March 6, 2014 12:54:22 AM UTC+1, puzzler wrote: > > The potential problem with modeling it as a knapsack problem is that it > assumes that grant-giving is an all-or-nothing affair. > Yes, exactly this. I realized I omitted this when I woke up in the middle of the night

Re: Solving allocation problems; code review and core.logic

Overall, though, I agree with Jordan's point. You don't really need any sophisticated constraint solving to solve the problem as you've described it -- the greedy approach works fine in this context. Simply sort all the applicants in descending order by score divided by amount of money requested,

Re: Solving allocation problems; code review and core.logic

The potential problem with modeling it as a knapsack problem is that it assumes that grant-giving is an all-or-nothing affair. Another reasonable way to model it is to assume that if I'm given, say $80 out of $100 requested, then I have an 80% chance of going. With such a model, let's say I have

Re: Solving allocation problems; code review and core.logic

Sounds like you might be able to model it as a knapsack problem with budgets as weights and scores as values. For a little intuition into what will happen, consider a greedy algorithm to solve the knapsack. Assuming that the individual budgets are relatively small compared to the total budget the

Re: Solving allocation problems; code review and core.logic

Hi David and Alex, Thanks for your replies! I'm having trouble communicating it, and the underspecifiedness doesn't help. Perhaps that just means I don't really understand the problem. Please let me know if any particular parts are hazy. What we *really* care about is getting people to the confe

Re: Solving allocation problems; code review and core.logic

I released a library yesterday called Loco, which might be what you're looking for. (David mentioned JaCoP, which is very similar to the Java library that Loco runs on.) You might also want to check out this blog post

Re: Solving allocation problems; code review and core.logic

I'm cross posting this to the miniKanren mailing list. It sounds like core.logic or cKanren could be applied to your problem but would need more details. I also wouldn't rule out finite domain solvers like JaCoP. David On Wed, Mar 5, 2014 at 9:52 AM, Laurens Van Houtven <_...@lvh.cc> wrote: >

Solving allocation problems; code review and core.logic

Hi! I've been experimenting solving some real-world problems related to organizing a sizable (2000-3000 people) programming conference with a strong open source flavor. My next problem is a bit more daunting. This conference has a financial aid program. People who can not afford to come to the