Yes! That's what I was looking for :). I really like the idea of 'team-centric' and 'player-centric', and combining them! It might take me some time to figure it all out in detail, but with this idea and your example, I'll pretty confident I'll get there :). I could go for heuristics as well, but in that case I need to be able to rate team assignments, which is not that easy. For now, I just want to have all possible solutions and some information about violations etc, and let the user choose one to continue with. A weighted score (based on user weights) might be used for optimization, but in in my experience, users are not always that good using 'weights' which result in one optimized solution. Leaving a choice often feels better, meaning: the user feels of having full control. Anyway... using a kind of weighted score for each team might be another 'feature' I might add, if I get the basic stuff to work :).
Thx a lot! Op woensdag 7 oktober 2015 06:48:06 UTC+2 schreef puzzler: > > Here is my Loco-based solution to the team-splitting problem: > https://gist.github.com/Engelberg/d8007588ce5a83fd0303 > > There is a whole art to building constraint programming models. I know > the basics, but I'm not an expert, and your model sounds fairly > complicated. So I'm not sure I can answer all your questions, but I can > point you in the right direction. There is a Coursera course devoted to > this which I've been meaning to take: > https://www.coursera.org/course/modelingoptimization > You might find that interesting as well. It uses minizinc, which has a > lot of similarities to loco (which wraps choco). There exists a clojure > wrapper for minizinc, but I have not used it. > > Your approach seems like a good possibility. I think, as you point out, > constrain spots 1 and 2 to being non-negative (since there must be players) > and then just adding more negative numbers to the range for spot 3 (as many > as there are teams) does the trick and then you can apply the $distinct > global constraint to all the spot variables. I would probably go one step > further and say that team t can only have a player number or the specific > negative number -t in spot 3. (So it doesn't waste time trying various > permutations of negative numbers in spot 3). > > Another possible approach is that each player is assigned a team number. > So variable t_i is the number of the team that player i is assigned to. > When doing something like this, you usually want to apply a > "symmetry-breaking strategy" by ensuring that the team numbers are assigned > in ascending order. To do that, you add constraints along the line: > t_i <= max(t_0, ..., t_i-1) + 1 > > You could then use the frequencies global constraint to make sure that > each team has only 2 or 3 players. > > In fact, it is possible to simultaneously use both representations, by > connecting them to one another: > for each player i, i should be in one of t_i's 3 spots. > > and then you are free to express each idea using either the player-centric > or team-centric view of things. > > Some of what you provide are logical constraints which can be enforced > using the appropriately modeled constraint. > > Then, you have a whole bunch of preferences you want to maximize and > violations you want to minimize. The general approach for doing that is to > "reify" each of these things to a variable where 1 is the bad scenario > (violation of rule, or lack of fulfilling a preference) and 0 is the good > scenario. The create a variable that sums these reified variables, and > minimize on that. > > I think for the scope of problem you're talking about (< 100 players), > loco could perform well for you. But if not, as I mentioned in the other > thread, there are a lot of simple heuristics that are fairly easy to > implement in Clojure. Once you have a way to rate your team assignments, > you just start with a random configuration and explore various swaps (this > may be a small enough number of players to explore all possible swaps from > a given state and go directly to the best rated result, otherwise use > random sampling). Multiple restarts, tabu search, simulated annealing are > all easy to implement and can yield great results. (Seems like building a > toolkit of these heuristics would be a fun library to put together for > Clojure!) > > > -- 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.
