Author |
Topic: Minimum-weight perfect matching (Read 8938 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Minimum-weight perfect matching
« on: Dec 30th, 2006, 9:54pm » |
 Quote  Modify
|
The floating elimination tournament format has some nice features, but one drawback is that it isn't obvious how to move from general features to a specific pairing. For example, we can say we want winners to play winners, we want to avoid repeated pairings, we want to give the bye to the top remaining player with no bye yet, etc., but given those agreed principles, how do we find the optimal pairing?
Paul Pogonyshev (author of bot_Aamira) generously provided some code which would find the globally optimal pairing, using branch-and-bound techniques. The great thing about his code is that we can plug in whatever formula we want, depending on what we value. For example, if we decide that it is good to give the bye to the lowest remaining player rather than the highest, we just need to change a formula in one place, and his code cranks out the globally optimal pairing under the new assumptions.
The problem with the code, however, is that branch-and-bound takes an exponential time in the worst case. Omar successfully ran Pogonyshev's program on a hypothetical 18-player tournament to test it out, and it worked fine, but when he tried to run it on our actual tournament of 20 players, the server crashed.
The workaround for this year was to use the simplistic pairing algorithm from last year, which finds the optimal pairing in easy cases. For the first two rounds, it worked fine, because repeat pairings were not an issue until the third round. And by the third round only 15 players remained, so Pogonyshev's code could be used from then on. This workaround, however, will only work for a tournament size up to 24 players, because if any more players enter, there will be more than 18 left in round three.
The good news is that an efficient algorithm for finding the globally best pairing is known. It could pair a tournament of hundreds of players in seconds. Our tournament pairing problem is known in operations research crowds as "minimum weight perfect matching", which was solved in O(n^4) time in 1965 by Jack Edmonds. That algorithm has been improved and re-implemented many times in the forty years since, so that O(n^3) is now considered outdated, although it is perfectly adequate for our purposes.
The bad news is that the efficient algorithm is not easy to describe. I will eventually attempt a description here so that some community-minded soul can implement it, for the larger good of Arimaa. Before I take that plunge, however, it pays to at least look for a free existing implementation.
When I search Google for variations on "minimum weight perfect matching" I keep hitting a 1999 paper by Cook and Rohe. That paper says their code is freely available from http://www.or.uni-bonn.de/home/rohe/matching.html. Sadly, the link is now dead. However, it is just possible that Andre Rohe is still at Universitaet Bonn, and that his code is still available for free. I tried to wade through the Web site to look for him among the faculty, but my German apparently isn't quite good enough for that.
PMertens, would you be willing to look up Andre Rohe, if he is still at uni-bonn? If we get his code, you will be spared a long-winded description of a moderately complex algorithm. 
|
|
 IP Logged |
|
|
|
woh
Forum Guru
Arimaa player #2128
Gender:
Posts: 254
|
|
Re: Minimum-weight perfect matching
« Reply #1 on: Dec 31st, 2006, 4:36am » |
Quote Modify
|
At the web site of Cook http://www2.isye.gatech.edu/~wcook/blossom4/ you can download the code for 'The Blossom IV Code for Min-Weight Perfect Matching'. To build it you'll need a library called concorde but there is a link where you can download this as well.
PS: when I had a look both links were really slow...
|
|
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Minimum-weight perfect matching
« Reply #2 on: Dec 31st, 2006, 5:52am » |
Quote Modify
|
thanks a lot ... saves me a lot of work 
I could dl the stuff at 50K .... not sure what is considered slow in Belgium 
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #3 on: Dec 31st, 2006, 8:16am » |
Quote Modify
|
Nice find, woh! I assume that Cook will let us use the code for a non-academic purpose, as long as we aren't making any money from it. I gather Blossom IV is optimized for geometric instances (i.e. where the weights are actually distances between points in a plane), which our pairing is decidedly not, but since we have such small numbers of nodes (players) the last ounce of efficiency doesn't matter as much as the fact that running time is asymptotically polynomial. We could be cracking a walnut with a sledgehammer here, but still it could be the easiest answer to our problem.
|
| « Last Edit: Dec 31st, 2006, 8:48am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #1
« Reply #4 on: Apr 13th, 2007, 11:21pm » |
Quote Modify
|
I found a book which describes Edmonds' minimum-weight perfect matching algorithm in enough detail that one could implement it. I believe I understand the description, but I am afraid my programming skills are not up to the coding task. Omar has suggested that I describe the algorithm so that he can implement it. I thought I might as well put the description up in the Forum so that Omar's code could be debugged and made more efficient by others that also understand what the algorithm is supposed to do.
However, before we even get started on the minimum-weight perfect matching, we need to come up with a matrix of weights which represent the "badness" of each pairing. How to generate those weights is an entirely separate discussion. We already agree about some things, for example that (winner vs. winner) and (loser vs. loser) should both have lower weights than (winner vs. loser), to encourage the algorithm to pick a pairing which keeps the losers' bracket separate from the winners' bracket. We don't all agree on other things, like folding pairing. We can hash out those differences later.
A perfect matching can only exist when there are an even number of players. If we have an odd number of players left, then we have to introduce an extra player called "bye". The weight for the pairing (Player X vs. bye) represents the badness of Player X getting a bye, so the weight will be huge if Player X already had a bye in an earlier round, astronomical if Player X has already had two byes, etc.
For the purposes of this description, I will assume we already have calculated the weight of each pairing, for an even number of players (2N), and I will assume all the weights are positive. The algorithm works fine with negative weights, but it makes the initialization step marginally more complicated, so we might as well disallow them.
We will start with an empty matching, and iterate N times, each time producing a matching containing one more pairing than the matching of the previous iteration. After the Nth iteration we will have N pairs, i.e. a perfect matching. Given that anyone can play anyone, it is not hard to pair everyone (i.e. not hard to find some perfect matching), but due to the extremely clever way we proceed, the matching we will produce at the end of our Nth iteration will be guaranteed to be the best one, i.e. one of minimum weight.
Players only join the set of paired players; they never leave it. Each iteration adds two players to the set of paired players. However, we don't necessarily keep all the old pairings from one iteration to the next. If the first iteration gave us the matching (A vs. B), the second iteration might produce the matching (C vs. A) and (B vs. D).
The augmentation will always take the form of a chain. For example, suppose that after four iterations we have the pairing (A vs. B), (C vs. D), (E vs. F) and (G vs. H). Suppose that on the fifth iteration we add the two players X and Y. Some of the possible ways we could add them are:
1. Put (X vs. Y) in.
or
2. Put (X vs. A) in, take (A vs. B) out, and put (B vs. Y) in.
or
3. Put (X vs. F) in, take (F vs. E) out, and put (E vs. Y) in.
or
4. Put (X vs. G) in, take (G vs. H) out, put (H vs. B) in, take (B vs. A) out, put (A vs. D) in, take (D vs. C) out, and put (C vs. Y) in.
There are many more possibilities, but all of them will be of this pattern, and any of them will leave us with one more pairing in our matching than we had before. Of course, we don't like building chains because it takes time, and we would rather do the simplest augmentation, so as soon as we find a "legal" augmentation (which I will define soon) we will halt the iteration and just add those players to the matching.
The first iteration is easy. Pick any player at random, look at the weight of his pairing with each opponent, pick the minimum weight, and pair those two players. Whee! One down, N-1 to go! If only it stayed that simple...
This forum limits the length of each post, and there is no way I am going to get the whole description into one post, so let me put in a page break here.
|
| « Last Edit: Apr 14th, 2007, 5:00pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #2
« Reply #5 on: Apr 14th, 2007, 9:36am » |
Quote Modify
|
OK, before I explain how each of our N iterations is going to find a legal augmentation, I had better step back and define what I mean by "legal". We are going to do some fancy bookkeeping which magically insures that the pairings we add to our matching are good pairings, i.e. pairings that make progress towards our minimum-weight perfect matching. We don't want to add some pairing of enormous weight to our matching unless we have to, because it may mess us up so much that later iterations can't fix it. In fact, the definition of a legal augmentation is exactly that it consists of "legal pairings". So what I really need to define here is when a pairing is good enough for us to consider adding to our matching.
However, whether or not a pairing is good enough depends in some sense on the two players involved in the pairing. You may have a player who is "hard to pair" because, for example, he has already played each of the other players once, so each of his possible pairings has a high weight. We can't avoid all of those high-weight pairings, because we have to pair him with somebody! It may turn out that one particular pairing with a high weight is actually very desirable, because it lets you pair a player who is otherwise extremely hard to pair, and you would have gotten an even worse weight if you paired him with anyone else.
Therefore we will introduce a second set of numbers, one for each player. Let's think of these numbers as showing how expensive it is to pair each player. For each player we now have an expense. This is in addition to having the weights we started with for each pair of players.
All of our expenses start at zero, because initially we don't know how costly each player is going to be. As we iterate, we will move player expenses up and down depending on who appears to be the bottleneck at any given time. It may turn out that a player who initially seemed very expensive later happens to be someone that lots of different people want to pair, which will make him seem more desirable, and which will reduce his expense number later.
While we are moving our expenses up and down, we will always obey a strict rule. The expense of A plus the expense of B will always be less than or equal to the weight of pairing (A vs. B). This is intuitive, right? It doesn't make any sense to say that A costs us 50 to pair, and B costs us 60 to pair, if the weight of (A vs. B) is only 80. If the weight of (A vs. B) is 80, then the combined expenses of A and B can be at most eighty, and will usually be less.
It is less intuitive, but still possible, for a player's expense to become negative, even though the weights are all positive. (The weights never change.) A negative expense can happen if one player is particularly desirable to pair. So in the above example where the weight of (A vs. B) is 80, it is possible for A to have an expense of 90 while B has an expense of -10. The important thing is that the sum of two players' expenses is at most equal to the weight of their pairing against each other.
Now that we have an expense for each player, we can define what pairings are good enough to be considered. A legal pairing is one that exactly matches the sum of the expenses of the two players. This also makes intuitive sense, right? If the weight of the pairing is greater than the sum of the two expenses, then the pairing is not good enough, because we think maybe we can substitute a different pairing with less weight instead.
The only trouble is that, at the outset, all pairings are illegal because we set all the expenses to zero! At the start, none of the pairings looks good enough to us because we are underestimating everyone's true expense. So one of our main tasks as we iterate is to increase everyone's expense as much as possible. We will be going back and forth between two problems, using each problem to determine the answer to the other problem. These two are called "dual linear programs" in math speak.
At the end of the day, we only want the best matching, and we don't give a hoot about expenses, but it turns out that we have to accurately calculate expenses in order to solve our real problem. We will use the expense of each player to help us find a low-weight matching, and we will use our low-weight matching to help us find the true expense of each player, in a kind of feedback loop. When we are done, the answer to each question proves that the answer to the other question is correct. This is a totally subtle mathematical point, which I certainly can't prove in the space of the forum, but let me just say that Edmonds must have been a genius to see how it would solve this problem. For mathematical correctness, you are just going to have to trust me.
Returning to our first iteration, I can now state it in terms of player expenses as well as in terms of player weights. Pick a player at random. It will appear that it is illegal to pair that player with anyone, but that is merely because we are underestimating the expense of everyone. Let us raise the expense of the player until some pairing becomes legal. When you think about it, there is only one way to do this. We are not allowed to raise the expense past any of the pairing weights, so we can only raise it up to the weight of the least bad pairing for that player. As soon as we raise the expense that high, the least bad pairing becomes legal. We add that pairing to our matching, and the first iteration is over. Whee! If only it stayed this easy...
An example may help clarify. Suppose our tournament has four players left, A through D, and the weights of their pairings are
(A vs. B) = 80
(A vs. C) = 25
(A vs. D) = 600
(B vs. C) = 15
(B vs. D) = 700
(C vs. D) = 500
Maybe D's weights are all high because he has played each of the other three earlier in the tournament. First, we initialize all of our player expenses to zero.
A=0
B=0
C=0
D=0
Now we choose any player. Let's say we choose C. None of C's pairings are legal.
(A vs. C) = 25, but combined expense = 0+0 = 0 < 25. Illegal
(B vs. C) = 15, but combined expense = 0+0 = 0 < 15. Illegal
(C vs. D) = 500, but combined expense = 0+0 = 0 < 500. Illegal
Therefore we have definitely underestimated expenses. We raise C's expense until some pairing becomes legal. This happens when C's expense is 15. Then we have
(A vs. C) = 25, but combined expense = 0+15 = 15 < 25. Illegal
(B vs. C) = 15, but combined expense = 0+15 = 15 = 15. Legal. Yay!
(C vs. D) = 500, but combined expense = 15+0 = 15 < 500. Illegal
We have now created a legal pairing, which turns out to be a legal augmentation as well. We add (B vs. C) to our matching, and the first iteration is complete. We also save the expenses
A=0
B=0
C=15
D=0
because we will need them when we start the next iteration.
|
| « Last Edit: Apr 14th, 2007, 5:14pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #3
« Reply #6 on: Apr 14th, 2007, 12:26pm » |
Quote Modify
|
Before I give a general way to find a legal augmentation, let's continue the above four-player example to get used to the idea of augmenting. We have so far paired (B vs. C), so we pick an unpaired player at random to add to the matching. Let's say we pick D. At the moment D has no legal pairings:
(A vs. D) = 600, but combined expense = 0+0 = 0 < 600. Illegal
(B vs. D) = 700, but combined expense = 0+0 = 0 < 700. Illegal
(C vs. D) = 500, but combined expense = 15+0 = 15 < 500. Illegal
We increase D's expense as much as we can. The nearest constraint is the pairing (C vs. D), which is 485 from being maxed out, because C already has expense 15. So we update the expense of D to 485, leaving our expenses at:
A=0
B=0
C=15
D=485
Now we have made (D vs. C) a legal pairing. Sadly, though, it isn't a legal augmentation, because C is already paired to B. We can't put (D vs. C) into our matching without taking (C vs. B) out of our matching. Swapping out one for the other doesn't increase the size of our matching, unless we can simultaneously swap in a new pairing for B.
Like the motivational speakers, we consider this an opportunity, not an obstacle. Instead of having one way to get a legal augmentation, i.e. finding an opponent for D, we have two ways to find a legal augmentation, i.e. finding an opponent for D or B. We will have an augmentation if we can get either of those guys paired.
In order to get a new legal pairing for D or B, we need to raise their expenses. Unfortunately, we can't raise D's expense without violating the maxed-out weight of (D vs. C). Also we can't raise B's expense without violating the maxed-out weight of (B vs. C). We are in a pickle. The solution isn't too hard, though. We can raise the expenses of both D and B, while simultaneously lowering the expense of C by exactly the same amount. If we do that, the pairings (D vs. C) and (B vs. C) both stay legal, and eventually either D or B will gain a new legal pairing.
So, how much do we raise D and B while lowering C? We look at how much slack all the pairing weights have left us:
(A vs. D) = 600, while combined expense = 0+485. Slack = 600-485 = 115.
(A vs. B) = 80, while combined expense = 0+0. Slack = 80-0 = 80.
(B vs. D) = 700, while combined expense = 0+485. Slack = (700-485)/2 = 107.5.
Did I surprise you by dividing by two in the third line? Remember that we are raising the expense of both B and D by the same amount. They have to rise in tandem, so that lowering the expense of C by an equal amount can keep both (B vs. C) and (D vs. C) legal. Thus the pairing (B vs. D) has half as much slack as you might think.
In any case (A vs. B) provides the tightest constraint with only 80 slack, so 80 is the amount by which we raise the expenses of B and D while lowering the expense of C. Our new expenses are:
A=0
B=80
C=-65
D=565
Note that we now have three legal pairings, and those three pairings make up a chain that is a legal augmentation. Let me list all the pairings just for completeness, although we don't really care about the illegal pairings since we aren't going to use them.
(A vs. B) = 80, combined expense = 0+80 = 80. Legal
(A vs. C) = 25, combined expense = 0-65 =-65 < 25. Illegal
(A vs. D) = 600, combined expense = 0+565 = 565 < 600. Illegal
(B vs. C) = 15, combined expense = 80-65 = -15. Legal
(B vs. D) = 700, combined expense = 80+565 = 645 < 700. Illegal
(C vs. D) = 500, combined expense = -65+565 = 500. Legal
We can augment along a chain of legal pairings. Put (D vs. C) in, take (C vs. B) out, and put (B vs. A) in.
That was our second iteration. Everyone is paired now, and we are done! Note that the sum of all the expenses is 580 and the sum of the weights in our perfect matching is also 580, i.e. 500 from (D vs. C) and 80 from (A vs. B). This is not an accident. Indeed, the equality is our guarantee. You could pick a different set of expenses that doesn't violate any weight, for example
A=40
B=40
C=-30
D=530
However, you could NOT find any set of expenses which totals more than 580 without violating some pairing weight. Similarly, I can find other perfect matchings, but not with a total weight of less than 580. Mathematically speaking, whenever the values of two dual linear programs are equal, then both are optimal solutions.
|
| « Last Edit: Apr 14th, 2007, 5:18pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #4
« Reply #7 on: Apr 14th, 2007, 8:05pm » |
Quote Modify
|
Eagle-eyed readers may have spotted me being tricky in the above example. For the second iteration I picked an unpaired player at random, namely D. This implies that I could have picked A just as well. However, if you go back and try to pick A instead, you will find that you get stuck. You won't be able to increase the expenses of A and B enough for either of them to get a legal pairing with D, because the weight of (A vs. B) gets in the way. So you might ask how I knew that picking D was correct.
Actually, the issue is worse than that. There are situations where you can get stuck no matter which unpaired player you use to start an iteration. Let me give one of these troublesome examples, and then explain how we are going to get around it.
Suppose we have a tournament of six players, A through F, seeded in alphabetical order. Suppose that in the first round A beats F, B beats E, and C beats D. Our task is to pair the second round, and we have generated the following table of weights:
| - | A | B | C | D | E | F | | A | - | 3 | 2 | 57 | 59 | 510 | | B | 3 | - | 6 | 54 | 506 | 57 | | C | 2 | 6 | - | 502 | 54 | 55 | | D | 57 | 54 | 502 | - | 2 | 1 | | E | 59 | 506 | 54 | 2 | - | 3 | | F | 510 | 57 | 55 | 1 | 3 | - |
The weights reflect the fact that we would like to pair winners against winners, and losers against losers. Also the weights reflect the fact that we really, really don't want to pair players who have already played each other. Some trial and error indicates that the best perfect matching is (A vs. B), (C vs. E), and (D vs. F) with a total weight of 57. It isn't easy to be sure this is best, even with only six players, but the number of reasonable cases is still small, so eventually one can feel confident.
However, if we try to assign expenses in the dual problem, we will end up with expenses like
A = 0
B = 3
C = 2
D = 0
E = 2
F = 1
for a total expense of 8. We can try all day to raise the expenses, but the total will never get up to 58. Indeed, the optimal set of expenses adds up to 8.5. Even worse, with these expenses, none of the pairings between a winner and a loser is legal. What went wrong?
It turns out that the dual solution corresponds to a matching that is essentially (A vs. B vs. C) and (D vs. E vs. F). If we could play three-way Arimaa, that probably would be the best way to do it. But since we are stuck with a two-player game, we have to find a way to exclude such degenerate solutions.
The problem arises because sometimes it is difficult to pair a whole group of players with any player outside of that group. If the group has an even number of players, we don't care that we can't pair outside the group, because we can pair them all internally. But if the group has an odd number of players, we have to pair someone inside the group with someone outside.
The workaround to this problem is in the spirit of assigning expenses to players. If we find an odd group that is difficult to pair, we assign an expense to the group as a whole, rather than to any player inside the group. To reflect the difficulty in pairing a winner to a loser, we need to give an expense to the group ABC or the group DEF. If we had the following set of expenses
A = 0
B = 3
C = 2
D = 0
E = 2
F = 1
ABC = 50
then the pairing (C vs. E) would be legal. To be more precise, a pairing is now legal if its weight is equal to the sum of expenses of the two players, plus the expense of any group that one of the players is in and the other player is not in. (C vs. E) has a weight of 54, which equals 2 (the expense of C) plus 50 (the expense of ABC) plus 2 (the expense of E).
We have to be just as careful with our group expenses as we were with our player expenses to never have any pairing with a weight less than the sum of the expenses. In the above example, we couldn't increase ABC to an expense of 51 because that would exceed the weight of (C vs. E). Also we couldn't have weights
A = 0
B = 3
C = 2
ABD = 5
because (A vs. C) has weight of only two, and the combined expense of 0 (A) + 2 (C) + 5 (ABD) is greater.
By now some folks' warning bells of algorithmic efficiency are probably going off. There are a ton of different odd groups when there get to be any sizable number of players. For fifty players, there are 344,680,279,929,482 different possible odd groups. How could we possibly find the best set of expenses when the number of variables is exponential? Fortunately, almost all of those expenses will be zero almost all of the time. We don't need to use all the variables to find an optimal solution; we only need a few. Indeed, we will never give an expense to more than N odd groups, and the groups will never overlap in funky ways; they will either be disjoint or nested.
The algorithm which incorporates odd groups is hard to explain in the abstract, so I would like instead to explain by example using the six-player table of weights given above. Afterwards I will try to define the algorithm more formally. This time through, instead of picking players randomly, I will start each iteration with the unpaired player who is alphabetically first.
Initialization: Set expenses to
A = 0
B = 0
C = 0
D = 0
E = 0
F = 0
Iteration one: select unpaired player A. Of the five possible pairings involving A, the most constraining is (A vs. C), with a slack of only 2. Therefore we increase the expense of A to 2, making (A vs. C) a legal pairing, and add this pairing to our matching.
State at end of first iteration:
matching = (A vs. C)
A = 2
B = 0
C = 0
D = 0
E = 0
F = 0
Iteration 2: select unpaired player B. Of the five possible pairings involving B, the most constraining is (B vs. A), with a slack of 1. Therefore we increase the expense of B to 1, making (B vs. A) a legal pairing. This doesn't finish the iteration because A was already paired.
A = 2
B = 1
C = 0
D = 0
E = 0
F = 0
In order to keep increasing the expense of B, we need to reduce the expense of A and increase the expense of C. This will keep both (B vs. A) and (A vs. C) legal. Also it will give either B or C a new legal pairing. So we check the constraints to increasing the expense of B and C:
(B vs. D) has weight 54, expense 1+0=1, slack 54-1=53
(B vs. E) has weight 506, expense 1+0=1, slack 506-1=505
(B vs. F) has weight 57, expense 1+0=1, slack 57-1=56
(C vs. D) has weight 502, expense 0+0=0, slack 502-0=502
(C vs. E) has weight 54, expense 0+0=0, slack 54-0=54
(C vs. F) has weight 55, expense 0+0=0, slack 55-0=55
(B vs. C) has weight 6, expense 1+0=1, slack (6-1)/2=2.5
By far the pairing (B vs. C) is the most constraining. We increase the weights of B and C each by 2.5, while decreasing the weight of A by 2.5. Our new weights are
A = -0.5
B = 3.5
C = 2.5
D = 0
E = 0
F = 0
This makes the pairing (B vs. C) legal. Unfortunately, we still don't have an augmenting chain, even though (A vs. B), and (B vs. C) and (C vs. A) are all legal. It's a closed circuit of three players. Although we could take any of those three pairings to be part of our matching we can't get more than one pairing out of it.
We need to find some way to get one of these three players paired outside the group. Curiously, we don't even care which of the three gets paired outside. For example, if C gets paired to someone else, we can use the legal pairing (A vs. B). It is as if ABC were a single entity requiring a partner.
Following this train of thought to its logical conclusion, we could spawn a sub-problem, namely pairing the four players D, E, F, and ABC. If we solve that problem, we will be able to expand our solution to a solution for the original six-player problem. There are some tricky bits to the collapsing and re-expanding, but the basic idea is to simplify the problem so we can keep making progress.
When we collapse A, B, and C into a single entity, we need to save all the all the possible pairings. We will have three different ways to pair ABC to D, one corresponding to each of (A vs. D), (B vs. D), and (C vs. D). This is necessary so that if we happen to pair (ABC vs. D), we will know which of the three original players gets the pairing when we expand back up to the original problem. So the collapse is actually all about getting a single expense for the group ABC, not about reducing the number of possible pairings.
Also, our collapsed problem must respect all the constraints of the original problem. How can we insure that, for example, the weight of (B vs. D) is never exceeded by the sum of expense of B, expense of ABC, and expense of D? There is no B in the collapsed problem. The answer is to reduce the weight of (B vs. D) by the expense of B in the collapsed problem, after which the constraints of the collapsed problem correspond to the original constraints. Thus we take the state:
| - | A | B | C | D | E | F | | A | - | 3 | 2 | 57 | 59 | 510 | | B | 3 | - | 6 | 54 | 506 | 57 | | C | 2 | 6 | - | 502 | 54 | 55 | | D | 57 | 54 | 502 | - | 2 | 1 | | E | 59 | 506 | 54 | 2 | - | 3 | | F | 510 | 57 | 55 | 1 | 3 | - |
A = -0.5
B = 3.5
C = 2.5
D = 0
E = 0
F = 0
and we collapse to the state
| - | ABC | ABC | ABC | D | E | F | | ABC | - | - | - | 57.5 | 59.5 | 510.5 | | ABC | - | - | - | 50.5 | 502.5 | 53.5 | | ABC | - | - | - | 499.5 | 51.5 | 52.5 | | D | 57.5 | 50.5 | 499.5 | - | 2 | 1 | | E | 59.5 | 502.5 | 51.5 | 2 | - | 3 | | F | 510.5 | 53.5 | 52.5 | 1 | 3 | - |
ABC = 0
D = 0
E = 0
F = 0
We are still in the middle of the second iteration, which started because we were trying to add player B to our matching. In our collapsed world that means we are trying to add player ABC to our matching. This means increasing the expense of ABC until some pairing becomes legal. The smallest constraint is 50.5, coming from the pairing (ABC vs. D). We increase the expense of ABC to 50.5. Now (ABC vs. D) is not only a legal pairing, it is a legal augmentation. We add it to our matching, and the second iteration is done. Whew!
I had better start another thread before hitting the length cutoff.
|
| « Last Edit: Apr 15th, 2007, 10:58am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #5
« Reply #8 on: Apr 15th, 2007, 10:47am » |
Quote Modify
|
Notice that, at the end of iteration 2, we didn't bother to re-expand our problem. There is no need. After we are totally done we can trace all the way back up to the perfect matching on the original problem. Sadly, there is one case where we might be forced to re-expand the problem in the middle of an iteration, but I'll explain that later.
We begin iteration 3 with the matching consisting of the pairing (ABC vs. D), the weights
| - | ABC | ABC | ABC | D | E | F | | ABC | - | - | - | 57.5 | 59.5 | 510.5 | | ABC | - | - | - | 50.5 | 502.5 | 53.5 | | ABC | - | - | - | 499.5 | 51.5 | 52.5 | | D | 57.5 | 50.5 | 499.5 | - | 2 | 1 | | E | 59.5 | 502.5 | 51.5 | 2 | - | 3 | | F | 510.5 | 53.5 | 52.5 | 1 | 3 | - |
and the expenses
ABC = 50.5
D = 0
E = 0
F = 0
For this iteration we attempt to add the unpaired player E. None of E's pairings are legal at present, so we need to increase E's expense. We check the six possible pairings to see which is most constraining:
(ABC vs. E) has weight 59.5; expenses total 50.5+0 = 50.5; slack=59.5-50.5=9
(ABC vs. E) has weight 502.5; expenses total 50.5+0 = 50.5; slack=502.5-50.5=452
(ABC vs. E) has weight 51.5; expenses total 50.5+0 = 50.5; slack=51.5-50.5=1
(D vs. E) has weight 2; expenses total 0+0 = 0; slack=2-0=2
(E vs. F) has weight 3; expenses total 0+0 = 0; slack=3-0=3
The most constraining is (ABC vs. E), so we increase E's expense to 1, making this pairing legal. Unfortunately, it isn't a legal augmentation, because we can't put (E vs. ABC) in without taking (ABC vs. D) out. As usual, this gives us two ways to win. We will increase the expenses of E and D in tandem, while reducing the expense of ABC, until either E or D gets a new legal pairing.
When we check the constraints to increasing D and E, note that all the ABC pairings don't enter into it, because ABC's expense is being reduced at the same time.
(D vs. F) has weight 1; expenses total 0+0 = 0; slack=1-0=1
(E vs. F) has weight 3; expenses total 1+0 = 0; slack=3-1=2
(D vs. E) has weight 2; expenses total 1+0 = 0; slack=(2-1)/2=0.5
We find that (D vs. E) is the most constraining, and limits us to increase the expense by 0.5. When we make that change our expenses become
ABC = 50
D = 0.5
E = 1.5
F = 0
and (D vs. E) becomes legal. But we are again in a pickle with an odd cycle, this time consisting of ABC, D, and E. We can pair any of the three to any other in the circle, but we can only get one total pairing out of it, so we can't augment. Furthermore, we can't increase the expenses without violating some constraint. Therefore, we pull out our favorite trick, and collapse the problem again! This time we merge ABC, D, and E into one entity. Remembering to reduce our weight by the current expenses, our newly collapsed problem becomes
| - | ABCDE | ABCDE | ABCDE | ABCDE | ABCDE | F | | ABCDE | - | - | - | - | - | 460.5 | | ABCDE | - | - | - | - | - | 3.5 | | ABCDE | - | - | - | - | - | 2.5 | | ABCDE | - | - | - | - | - | 0.5 | | ABCDE | - | - | - | - | - | 1.5 | | F | 460.5 | 3.5 | 2.5 | 0.5 | 1.5 | - |
with expenses
ABCDE = 0
F = 0
Recall that we started the iteration trying to pair player E, which falls into the collapsed problem as trying to pair player ABCDE. We increase ABCDE's expense as much as possible, which is 0.5 in this case, resulting in (ABCDE vs. F) becoming a legal pairing. This is also a legal augmentation, so we add the pairing to our matching. This completes the third iteration.
What's more, now that we have made three pairings, we are done with the problem as a whole. It only remains to expand the collapsed problem and recover the corresponding pairing in our original problem. In the first expansion, from (ABCDE vs. F), we recover (D vs. F). Since D was paired out of our cycle (ABC vs. D), (D vs. E), and (E vs. ABC), and D can't be paired twice, we are left to put (E vs. ABC) into our matching.
If we expand (E vs. ABC), we get the pairing (E vs. C). Since C was paired out of our cycle (A vs. B), (B vs. C), and (C vs. A), we are forced to put (A vs. B) into our matching. Thus our perfect matching in the original problem is (D vs. F), (E vs. C), and (A vs. B), just as we originally expected.
The total weight of our matching is 58. Note that our final expenses were
A = -0.5
B = 3.5
C = 2.5
ABC = 50
D = 0.5
E = 1.5
ABCDE = 0.5
F = 0
which not coincidentally adds up to 58. As before, this is our guarantee of an optimal solution, and now the optimal solution only includes games between pairs of people. Yay!
|
| « Last Edit: Apr 15th, 2007, 11:16am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Algorithm Description #6
« Reply #9 on: Apr 15th, 2007, 6:56pm » |
Quote Modify
|
Now that I've worked all the way through a small example, let me try to be more general about what each iteration is doing. In the examples, when I picked an unpaired player to add to the matching, I always found an augmentation in a few steps. It doesn't have to be that quick.
For example, I could be trying to add player X to the matching. I raise X's expense until some pairing becomes legal, say (X vs. A), but I can't add that to the matching because (A vs. B) is already in the matching. So I raise the expenses of X and B while lowering the expense of A until some pairing becomes legal, say (B vs. C), but I can't add that to the matching because (C vs. D) is already in the matching. So I increase the expenses of X, B, and D, while lowering the expenses of A and C until some pairing becomes legal, say (B vs. P), but I can't add that to the matching because (P vs. W) is already in the matching, etc. I could build up quite a tree before finding a legal augmentation, something like
Code:
X---A===B---C===D---E===F
| . \ . \
| . \ . \
M===N . P===W Q===V
|\
| \
H===G L===Z
|
|
In the above tree, each line represents legal pairing, i.e. pairings with a weight equal to the sum of the expenses of the two involved players. The heavy lines indicate pairings that are in the current matching. The dots are meaningless but I have to add them to prevent the forum from collapsing the spaces.
On each step we would be raising the expense of everyone an even distance from the root, including the root, namely {X, B, D, F, N, W, V, H, Z} and would be lowering the expense of every player an odd distance from the root, namely {A, C, E, M, P, Q, G, L}. The amount of change to all of these expenses is minimum of three things:
1) the minimum slack in any pairing which has one player in the even set and another player that is in neither of the two sets.
2) half the minimum slack in any pairing which has both players in the even set.
3) the minimum expense of any player in the odd set that is actually a collapsed group.
The third constraint comes from the fact that, although an individual player can have a negative expense, a group of players can't have a negative expense. There is a mathematical reason a group can't have a negative expense, while a player can, but in addition to the math it also sort of makes sense intuitively. We don't care if a group is really easy to pair to someone outside. In fact it might have multiple easy ways to pair outside, and we don't want to give a bonus for each. For example, consider the weights below:
| - | A | B | C | D | E | F | | A | - | 100 | 100 | 100 | 100 | 1 | | B | 100 | - | 100 | 100 | 1 | 100 | | C | 100 | 100 | - | 1 | 100 | 100 | | D | 100 | 100 | 1 | - | 100 | 100 | | E | 100 | 1 | 100 | 100 | - | 100 | | F | 1 | 100 | 100 | 100 | 100 | - |
The minimum-weight perfect matching is obviously (A vs. F), (B vs. E), and (C vs. D), with a total weight of 3. Also the maximum total expense we could find is three, for example
A = 1
B = 1
C = 1
D = 0
E = 0
F = 0
But if you allow groups to have negative expenses, you could find silly expenses like
ABC = -99
A = 50
B = 50
C = 50
D = 50
E = 50
F = 50
which reflects how easy it is to pair someone inside ABC to someone outside ABC. It's so easy we do it three times! The negative group expense gives us a new total expense of 201, which is unrelated to reality. So, to stop such nonsense, every group must have a weight of zero or above.
This raises the question of what to do when our tree can't grow any more due to hitting constraint #3. Let's suppose we were stuck because player Q in the tree above was really player QRSTU that we collapsed earlier.
Code:
X---A===B---C===D---E===F
| . \ . \
| . \ . \
M===N . P===W QRSTU===V
|\
| \
H===G L===Z
|
|
If QRSTU has expense zero that we can't lower any more, then we can't raise the expenses we need to raise. This is the situation I alluded to earlier where we have to expand a collapse before the end of the algorithm. But how to expand in the middle of building a tree?
The way we expand depends which player inside the cycle QRSTU the player V is paired with. Since QRSTU is an odd cycle, there will alway be an even-length path around one side and an odd-length path around the other side. We keep the even-length path in our tree and throw the rest away. For example, suppose it expands to
Code:
X---A===B---C===D---E===F
| . \ . \
| . \ . \
M===N . P===W Q===R---S===V
|\ . . \ . /
| \ . . \ /
H===G L===Z . U===T
|
|
Then we throw away the odd-length Q-U-T-S and keep the even-length path Q-R-S, for an updated tree
Code:
X---A===B---C===D---E===F
| . \ . \
| . \ . \
M===N . P===W Q===R---S===V
|\
| \
H===G L===Z
|
|
After the expansion Q and S represent players, not groups, so we can reduce their expenses in order to grow the tree, even if they need to be reduced to negative numbers.
We can only expand groups with zero expense. The expenses of the constituents of that group, however, can be anything. We have to remember to add their expenses back into the weights of the pairing. In the above example, the pairing (S vs. V) will have a weight equal to the expense of S plus the weight of the disappearing pairing (QRSTU vs. V), and similarly for all other pairings involving QRSTU.
I think I have finally explained all the weird conditions. Just to be clear, the algorithm branches depending on which type of constraint we run into when trying to grow the tree. Consider the cases
1) the minimum slack in any pairing which has one player in the even set and another player that is in neither of the two sets.
2) one half the minimum slack in any pairing which has both players in the even set.
3) the minimum expense of any player in the odd set that is actually a collapsed group.
In case #3, we adjust all the expenses, and then expand the collapsed group whose expense we just reduced to zero
In case #2, we adjust the expenses, and we notice that we have formed an odd-length cycle, which we collapse into a single pseudo-player in the tree
In case #1, we adjust the expenses, and add the newly made legal pairing to our tree. If that player was already paired, we have to add his pairing to the tree and keep on growing. If, however, we managed to connect to a previously unpaired player, we can trace the augmenting path all the way back up to the root, swapping pairings into and out of our matching, ultimately increasing the matching to one pairing more than it had before. That's another iteration completed.
The book suggests that we don't have to throw away all the bits of tree that might be left over after an iteration. I am not sure how this works in the data structure, but apparently if we are growing a new tree on the next iteration, and we hit a piece of tree that was left over from before, we can incorporate it directly into the new tree we are growing.
That's everything I can think of. Any questions?
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Minimum-weight perfect matching
« Reply #10 on: Apr 16th, 2007, 7:53am » |
Quote Modify
|
Thanks for that increadible explaination Karl. It's going to take me some time to digest this. It will be really great to eventually have a program that implements this.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #11 on: Apr 17th, 2007, 1:55pm » |
Quote Modify
|
Great story, yes! I was always eagerly waiting for the next part. And you didn't disappoint your readers ...
I just have a few simple questions first:
on Apr 13th, 2007, 11:21pm, Fritzlein wrote:I found a book which describes Edmonds' minimum-weight perfect matching algorithm in enough detail that one could implement it.
|
|
This seems to be an interesting book. Do you mind to mention the author and title?
Quote:
2. Put (X vs. A) in, take (A vs. B) out, and put (B vs. Y) in.
or
3. Put (X vs. F) in, take (F vs. E) out, and put (E vs. Y) in.
|
|
What's the difference? Or was 3.) supposed to have another pair involved?
Quote:
Then we throw away the odd-length Q-U-T-S and keep the even-length path Q-R-S, for an updated tree
|
|
What does actually happen to the pair U==T? Shouldn't U remain a child of Q?
I first thought collapsing could be implemented through recursion but because of possible expansions this might not be very useful.
After an expansion, can you easily "restore" the weight matrix?
As you understand the algorithm very well now, could you transform it into a structogram?
Or is there any (partial) pseudo-code provided in the book?
I started my own structogram but first need to understand a few more things.
Thanks a lot!
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Algorithm Description #1
« Reply #12 on: Apr 17th, 2007, 2:34pm » |
Quote Modify
|
on Apr 17th, 2007, 1:55pm, BlackKnight wrote:| Great story, yes! I was always eagerly waiting for the next part. And you didn't disappoint your readers ... |
|
Wow, I didn't know I had any readers; I was just having fun writing. Thanks for the positive feedback! Maybe I should serialize publication of algorithms like Charles Dikkens used to do for novels. (Note: name intentionally misspelled because the Forum censors "thingy
ens")
Quote:| This seems to be an interesting book. Do you mind to mention the author and title? |
|
The book is "Combinatorial Optimization", with William Cook as co-author. Presumably this is the same Cook whose blossom algorithm code is available for academic use, as mentioned earlier in this thread. Other co-authors are Cunningham, Pulleyblank, and Schrijver.
Quote:| What's the difference? Or was 3.) supposed to have another pair involved? |
|
Hmmm, I think I included that example to make the point that we can use pairings in either order as we make our chain, i.e. (F vs. E) instead of (E vs. F).
Quote:| What does actually happen to the pair U==T? Shouldn't U remain a child of Q? |
|
No, U can't remain a child of Q, because the path from X to U is not alternating. If we try to swap in (D vs. Q) then we can't also swap in (Q vs. U), no matter what we swap out, because Q can pair only one player. Similarly we can't swap in both (R vs. S) and (S vs. T), even if we swap out (S vs. V).
I can see that my explanation of which part of the cycle to throw away is a bit mystifying, but it comes from trying to retain the property that all paths out of the root are alternating between pairings we would like to swap in, and parings we would have to swap out, until we can find a path of this type terminating at an unpaired player.
Quote:| I first thought collapsing could be implemented through recursion but because of possible expansions this might not be very useful. |
|
The book explains that spawning copies of the problem can have some conveniences, but the worst-case running time is O(N^4). If, instead, you merge the nodes "virtually", the worst-case running time can be reduced from O(N^4) to O(N^3). They explained the data structure necessary to efficiently do the merges and splits in a different section of the book which I didn't read. I thought maybe the important thing was to get us from exponential running time down to O(N^4)...
Quote:| After an expansion, can you easily "restore" the weight matrix? |
|
You probably can, if you are more clever than I am.
Quote:| Or is there any (partial) pseudo-code provided in the book? |
|
I will transcribe the condensed description of the algorithm when I have it in front of me.
[EDIT: Actually, the pseudocode in the book relies so heavily on notation that it's basically useless out of context.]
Quote:
It is quite literally my pleasure.
|
| « Last Edit: Apr 17th, 2007, 9:13pm by Fritzlein » |
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: Minimum-weight perfect matching
« Reply #13 on: Apr 18th, 2007, 10:48am » |
Quote Modify
|
this is indeed quite interesting. I have a book on algorithms that could benefit if rewritten by someone such as yourself. Except, of course, for the code sample part- the authors collaborating with you might be worthwhile though.
I'll see if I can make any sense of combining the logic you described, with any of the algorithms that it provides code to implement, and if it does there might be a fairly efficient way to work it into something usable.
The only problem, of course, is that I don't seem to have enough free time to ever finish anything like this lately...
one would have though that after shipping Vista my group would have some free time. No, it was just catch-up time, and was spent before we ever earned it... 
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #14 on: Apr 18th, 2007, 4:30pm » |
Quote Modify
|
on Apr 13th, 2007, 11:21pm, Fritzlein wrote:| However, before we even get started on the minimum-weight perfect matching, we need to come up with a matrix of weights which represent the "badness" of each pairing. How to generate those weights is an entirely separate discussion. We already agree about some things, for example that (winner vs. winner) and (loser vs. loser) should both have lower weights than (winner vs. loser), to encourage the algorithm to pick a pairing which keeps the losers' bracket separate from the winners' bracket. We don't all agree on other things, like folding pairing. We can hash out those differences later. |
|
So the weights to be assigned to pairs might just be approximations.
Do we really need a minimum weight perfect matching then, and how good is good enough?
Maybe we could use an approximation algorithm. Even Greedy's performance is only twice as bad as the optimum. Those algorithms are much simpler to implement.
Is there a link to the current pairing script? I only found a link to the pairing script for the postal.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print