On Fri, Mar 7, 2014 at 3:50 AM, Mark Engelberg <mark.engelb...@gmail.com>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 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. > Eek! When you said slow, I was thinking "ten minutes", not "you're gonna need a bigger universe" :-D It does appear the numerator is the big culprit; so even constraints like "all people get between zero and two thousand dollars with 100 increments only" don't fix it. 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. > No worries, it was fun :-) > 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. > I don't know if you saw my original code; it's something I would describe as greedy + linear. I can use that as a starting point for tabu search maybe :-) hth lvh -- 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.
