finding optimal pairs/triplets

88 views
Skip to first unread message

Kurt Sys

unread,
Oct 6, 2015, 6:10:23 AM10/6/15
to Clojure
Reading the thread: generate al possible teams, I realized I was facing a slightly similar problem. Although many valuable suggestions were made, I'm very interested in one made by puzzler, i.e. using loco (unless another method/library is more useful, suggestions are welcome).

Now, the problem description:
1/ I have a set of players which must be divided in teams of two. If only teams of
two is not possible, teams of three are allowed as well.
2/ Every player has a set of characteristics. Based on these characteristics, some teams are not allowed, some are, and some are prefered.

There are quite a few characteristics, so I'll build up the first few:
1/ The main characteristic is 'level', ranging from 0-7. Only teams of two with total level of 5 or more are allowed.
For teams of three, there are separate rules: there must be at least one level 3. If the highest level is 3, than no two levels 1 or less are allowed.

2/ There is a characteristic 'experience' as well. Taking into account the exprience, there are more exceptions:
A level 3 and a level 1 is allowed (in contrast to rule 1: total should be at least 5), if the experience of level 1 is high enough
A level 4 and a level 1 are not allowed together, if the experience of level 1 is not high enough
Two levels 2 are allowed, if both are experienced enough

So far, it's still pretty easy to find a solution: rank according to level and experience, and take each time the top and bottom from the list. That should be pretty close to the most optimal solution. But there are more characteristics for each player:

3/ There are preferences to put some players together, scored from 1 (avoid teaming them) to 7 (high preference to team them). Based on these preferences, 'team preferences' might be calculated. If no 'preference' is given, a value of 4 is assumed. In this example, I scored them per player, but it might be done per team as well.

4/ Some players might have a 'handicap', so they need another levels to team with. If possible, the handicaps should be used, but they may be omitted if there is no other solution. In an extended version, a preference level for a handicap for a certain player may be set as well.

There are quite a few of handicaps (like 4) and rules (like 1 and 2, which are just a small subset of all handicaps and rules.

The number of players will not be very high, up to max 100, so max 50 teams, which might be important, since I don't think heuristics will have a high benefit in this case (but I might be wrong).

An example:

The players:
P1 {:level 0 :experience 0}
P2 {:level 2 :experience 17}
P3 {:level 3 :experience 23 :handicap :cl }
P4 {:level 3 :experience 27 :preference {P2 2, P3 6}}
P5 {:level 6 :experience 50}
P6 {:level 5 :experience 55 :preference {P2 1}}

The handicap description: {:cl :needs-level 5}

The solution?
(solve [P1 P2 P3 P4 P5 P6])
results in a set with possible solutions (possibly with some timeout or after the first x solutions are found):
#{
  { [ [P6 P1] [P5 P2] [P4 P3] ]
    :unmatched-handicaps 1
    :team-preferences [4 4] [4 4] [4 6] }
  { [ [P5 P1] [P6 P2] [P4 P3] ]
    :unmatched-handicaps 1
    :team-preferences [4 4] [1 4] [4 6] }
  { [ [P5 P3] [P6 P1] [P4 P2] ]
    :unmatched-handicaps 0
    :team-preferences [4 4] [4 4] [2 4] }
  ... }

Since puzzler said 'I can provide an example of that if you are interested' (for generating 'balanced teams' with restrictions with loco)... I'm interested :).

Thanks.

Kurt Sys

unread,
Oct 6, 2015, 10:22:55 AM10/6/15
to Clojure

So, the basic idea is to construct a matrix like this:
         spot1  spot2  spot3
team1      5      0      -1
team2      4      1      -1
...


With the 'spots' the spaces to fill in for each team. There are max 3 spots/team. If a spot is not used, -1 should be put. If it is used, I put the number of the player (index in the defined vector). For example, with a very small player vector:
(def players [{:level 3} {:level 4} {:level 7} {:level 1}])


The problems I'm facing so far:

1/ using $distinct to make sure each player is only assigned one spot on one team.
The value of -1 can be used more than once, because it's used as filler where no player is assigned.

(defn base-model [players]
 
(concat (for [team (range (quot (count players) 2)), spot (range 3)]
   
($in [:p team spot] (range -1 (count players)) ))))
 
(def all (for [team (range (quot (count players) 2)), spot (range 3)]
 
[:p team spot]))

(solutions (conj (base-model ps) ($distinct all) ))


doesn't give any solutions, obviously: there are always more possible spots to fill than there are players. A work-around would be to add more negative numbers as 'fillers', and adding some other constraints so that at least two of the three spots per team are positive. I'll make sure the vector is sorted anyway, on level first and experience second (with the player having the highest number in the front of each team, as captain), so that might be rather easy to do.
But it feels rather hacky.

2/ getting player data with $nth, so constraints based on player characteristics can be added.
For example, if I want player of team 1 on slot 1 having a level of more than 2, I'd expect something like this to work:
(solutions (conj (base-model ps) ($> (:level ($nth players [:p 0 0])) 2)  ))
which translates to me: take player on index given by [:p 0 0] from 'players', get the level from that player and check if it's higher than 2.
This, however, does not work:
IllegalArgumentException No method in multimethod '->choco*' for dispatch value: null  clojure.lang.MultiFn.getFn (MultiFn.java:156)
I clearly misunderstand how $nth (or how loco in general) works. How I can use my player characteristics (the vector of player data maps) for adding constraints?

Thx, qsys




Op dinsdag 6 oktober 2015 12:10:23 UTC+2 schreef Kurt Sys:

Alex Engelberg

unread,
Oct 6, 2015, 11:50:37 PM10/6/15
to Clojure
Loco's constraints and expressions only work on integers, so unfortunately $nth can't handle maps in a list. $nth takes either a list of Loco expressions or a list of integers. To get the nth player level, you could try:
($nth (map :level players) [:p 0 0])

Also, I should mention that all Loco constraints (anything beginning with $, really) don't really return any values of substance, they just return a map of constraint data to be used by other constraints and the solving function. So your usage of ":level" is not going to behave how you expect (it will just return "nil" because the return value of $nth has no :level key).

Let me know how my alternative solution works for you.

Thanks!
--Alex

Mark Engelberg

unread,
Oct 7, 2015, 12:48:06 AM10/7/15
to clojure
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!)


Kurt Sys

unread,
Oct 7, 2015, 2:52:18 AM10/7/15
to Clojure
Allright, makes sense... I must have mist the 'integer only' for all expressions (including $nth). Using 'map' seems to be doing what I expect (at first sight).

Thx!


Op woensdag 7 oktober 2015 05:50:37 UTC+2 schreef Alex Engelberg:

Kurt Sys

unread,
Oct 7, 2015, 3:09:48 AM10/7/15
to Clojure
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:
Reply all
Reply to author
Forward
0 new messages