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, > working with grant "tokens" each worth $50 or $100 or so? > > Not really. Let's do a little back-of-the-napkin estimate. Let's say you have 3000 attendees, each of whom can be granted $0, $50, $100, $150, ..., or $500. (That's 30,000 possible $50 "bins" to put money in). Then let's say that you have $20,000 of funds to parcel out in increments of $50 (a total of 4000 parcels to give out). So the number of possible ways to divvy this up is 30,000 take 4000 which is nearly 10^5114 possibilities. Clearly that's intractable even with $50 buckets. I apologize for getting your hopes up about Loco as a tool for this problem. I've been using it a lot lately, and when I saw you describe your problem, and saw David Nolen suggest JaCoP for consideration, I immediately thought, "Oh, I know how to model that in Loco." And yes, I did know how to model it, but I just didn't properly think through the ramifications of whether it would work for the size problem you're talking about. With further thought, I don't think any constraint solver would be able to tackle this. LP solvers exploit the linearity of the math constraints and the lack of any need for the result to be an integer in order to much more rapidly converge on a solution. Local search exploits the fact that you don't really care to prove that you have the optimal solution, you just need to find a solution that's really good. So, for example, you would start by divvying up the money in a greedy way, and then randomly shift around money looking for ways to improve the situation, occasionally taking a suboptimal choice in order to avoid getting stuck in a local optimum. Honestly, I do think that the greedy approach, based on the linear model we discussed at the beginning, will give you a good, practical solution that's close enough to optimal to be worthwhile. --Mark -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
