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 > whole budget to speed things up, and set a timeout, but the quality of the > solutions after a reasonable timeout is low. It's even worse with the > quadratic versus linear model, and with the quadratic model you have to be > careful in the scaling to avoid bumping into the upper bound on integer > values.) >
The good news is that the entire conference has fewer than 3000 attendees, so definitely far fewer than 3000 people in the financial aid system, so as long as that's feasible we're good :-) > This isn't too surprising. Constraint solvers like loco shine when the > constraints really limit the number of feasible solutions, and you are > simply minimizing/maximizing to optimize among those feasible solutions. > In this case, every possible allocation of dollars among the 3000 users up > to their requested limits is a *feasible* solution (doesn't violate any > constraints), so this becomes primarily an optimization problem *not* a > find-the-feasible-answer problem, which is not really what constraint > solvers are good at. > 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? (By the way, I noticed that your examples use indices; I'm presuming there's nothing wrong with using the applications themselves? Perhaps it's just impractical in ways I haven't discovered yet?) > If you don't mind the linear formulation, you could either go with the > greedy approach or use a linear programming solver (there aren't any good > Java/Clojure lp solvers, but it's not too hard to use Clojure to generate a > file that you can feed into something like SICP). > > Otherwise, you'd want to use a technique like local search (simulated > annealing or tabu search), which is relatively easy to code up in Clojure > (don't really need to use an external solver engine for this). > > If you want to become an expert at all these approaches, and deeply > understand what techniques work best for what kinds of problems, I highly > recommend the coursera course on Discrete Optimization, which > coincidentally began a new session a few days ago: > > https://www.coursera.org/course/optimization > As much as I would love to learn, I'm convinced that this is probably way outside of how much time I can spend on it :) thanks! 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/groups/opt_out.
