How the Scheduler Works (In Detail):
Since first introducing our Scheduler back when GolfTripGenius.com was released, we have been asked two questions by some curious customers after they see the sorts of perfect pairings that we produce:
Why is this problem so hard?
How do we solve the problem?
In this article, for those interested, we will explain why the problem is so hard and then talk in general terms about how we solve the problem.
To appreciate why this is a hard problem, you do not need to be a math jock, but just understand a couple of basic concepts from your first course in probability.
Let's start out with a really simple case of a league with just 8 golfers -- two foursomes. How many was are there to place 8 golfers into 2 foursomes?
Think back to the grade school playground where you and I were the captains for softball and had to select our teams. All of the other kids lined up. You picked your first player, then I picked my first player from those left, and so on. If you were good at math, you were probably the last guy picked, and this does not bring back great memories.
Let's apply the same idea to picking golfers, but in this case we just want to pick 4 golfers from the 8. For your first pick, you can choose any of 8 golfers. For you second pick, you can choose any of remaining 7 golfers. For your third pick, you can choose any of 6 golfers, and finally you choose any of 5 golfers for the 4th golfer in the foursome. How many ways are there to choose these 4 golfers from among the 8. There are 8 times 7 times 6 times 5 ways, right? That's 1,680. So we could conclude that there are 1,680 ways to group 8 golfers into two foursomes. Not so fast. Among those 1,680 permutations (see how I snuck that fancy word in) are, for example, [1, 2, 3, 4], [2, 3, 1, 4] and [5, 6, 7, 8]. There are two issues here. First it does not make sense to count [1, 2, 3, 4] and [5, 6, 7, 8] as two different cases. If we pick [1, 2, 3, 4], then [5, 6, 7, 8] is left as the other foursome. Furthermore, among these 1,680 permutations are all the ways of selecting 1, 2, 3 and 4: [1, 2, 3, 4], [1, 2, 4, 3], [4, 3, 2, 1] , etc.
How many different ways are there to order the numbers 1, 2, 3 and 4? We could choose any of them for the first position, then any of the three remaining for the second position, then any of the two remaining for the third position (and any of the one remaining for the last position). So there are 4 times 3 time 2 ways to order these four numbers, and that's 24. So, out of the 1,680 permutations of taking 4 golfers out of 8, 24 of them just have different orderings of 1, 2, 3, and 4. We don't care about order, do we? So we can divide 1,680 by 24 to get 70 different "combinations". That's not very many. But it gets even better. Of these 70 combinations for taking 4 golfers out of 8 are [1, 2, 3, 4] and [5, 6, 7, 8]. There are the same to us because they both have the same pairing; one is [1, 2, 3, 4] and [5, 6, 7, 8], and the other is [5, 6, 7, 8] and [1, 2, 3, 4]. So we can divide 70 by 2, and determine that there are 35 partitions for dividing 8 golfers into two groups of 4. Anyone could easily and quickly write down and examine these 35 partitions. So what's the problem here? We went from 1,680 permutations to 70 combinations to 35 partitions in probability-speak.
Let's make the giant leap from 8 golfers all the way to 12 golfers:
"The number of combinations of k golfers out of n golfers is equal to the number of permutations divided by the factorial of k". Don't faint on me here. First the factorlal of k (described as k!) is just the product of all numbers from 1 to n. 3! is 1 * 2 * 3 = 6, and 4! is 1 * 2 * 3 *4, or 24. Armed with that tidbit, let's look at 12 golfers to be divided into three foursomes. The number of permutations for the first foursome (ways to select 4 golfers out of the 12) is 12* 11 * 10 * 9 = 11,880. But we know that any set of 4 golfers will come up 24 times in this list of 11, 880 because there are 24 ways to order the 4 golfers ( [1, 2, 3, 4], [1, 2, 4, 3], etc. ). Hey - what's 24 - it's 4!. And 11,880 divided by 24 is 495, so there are 495 combinations for taking 4 golfers out of 12.
Ok, there are 495 ways to select 4 golfers out of 12, if we do not care about order within this foursome, which we do not. Now we're left with 8 golfers. We already know that there are 70 combinations for selecting 4 golfers out of 8. If there are 495 ways to select the first four and 70 ways to select then next four, then there are 495 * 70 (34,650) ways to divide the 12 golfers into three foursomes, as in [1, 2, 3, 4] for the first, [5, 6, 7, 8] for the second, leaving [9, 10, 11, 12] for the last foursome. But, one of these 34,650 is [1, 2, 3, 4] [5, 6, 7, 8] [ 9, 10, 11, 12] and another is [9,10, 11, 12] [5,6, 7, 8] [1, 2, 3, 4]. They're all the same to us, right? Since there are three foursomes, we can set any one of them as the first, and any of the remaining two as second. Hence, there are 3 * 2 = 6 different ways to order these three foursomes. So if we divide the number of combinations (34,650) by 6 (oh, isn't that the factorial of the number of groups?), we get 5,775 ways to partition 12 golfers into three groups of 4.
With 8 golfers, there were just 35 possible pairings. With 12 golfers that number jumps to 5,775. Are we getting a bit nervous? For each of these 5,775 possible pairings, we need determine if it is the best possible pairing given the actual pairings in all the previous rounds.
So we have a fairly simple way to determine the number of unique pairings for any size group, and to keep life simple let's just consider groups that are a multiple of 4. Here is what we do:
Determine how many permutations there are for the first foursome. For 16 golfers (we're really stepping it up here), there are 16 * 15 *14 *13. Then, divide by 24 (4! or 4 * 3 *2) to boil this down to the number of combinations.
Do that for each remaining foursome, multiplying them together as we go along, just as we multiplied 495 by 70 when dealing with 12 golfers.
Now divide by the factorial of the number of groups to get to the number of partitions - which is the number of unique pairings given that we do not care about the ordering of foursomes or the ordering of the four players within a foursome.
Well, that's pretty easy, and we just had to understand permutations, combinations and partitions.
Now let's "scale up" as we geeks say, and look at the number of ways to place 36 golfers into 9 foursomes. Let's proceed as we did above. The number of combinations of 4 golfers out of 36 is 58,905 (which is 36 * 35 *34 * 33, all divided by 24). That's not a big number. The number of combinations for selecting the next 4 golfers from the remaining 32 is 35,960. Oh my, we need to multiply those numbers together according to my recipe (we geeks would call that an algorithm). That's just 2,118,223,800 and in the land of fast computers that's not a big number. But --- and here is where you need to fasten your seatbelt -- the number of combinations of 4 golfers from the remaining 28 is 19,656; four out of 24 is 10,626; four out of 20 is 4,845; four out of 16 is 1,820 four out of 12 is 495 and four out of 8 is 70.
So how much, just out of curiosity, is 58,905 * 35,960 * 19656 *10,626 *4,845 * 1,820 * 495 *70 ? It's roughly 1 followed by 29 zeros, or one trillion times one trillion times 100,000. But wait, we need to divide by the factorial of the number of foursomes (9!) to get the number of unique partitions of 36 golfers into 9 foursomes. 9! is 362,880, so when we divide that really big number by 362,880, we are left with a bit less than 4 followed by 23 zeros -- 3.75 times 10 to the 23rd power, to be exact.
What is this "10 to the 23rd power" stuff. It's called scientific notation - it's a hell of a lot easier to write "10 to the 23rd" than it is to write down 23 zeros. A quick reference point: 10 to the 6th is a million, 10 to the 9th is a billion, 10 to the 12th is a trillion, ten to the 24th is a trillion trillion - and roughly equal to the number of stars in the universe.
We're dealing with some really big numbers here, but aren't computers supposed to be really, really fast? Let's see. The Scheduler runs on 10 computers at the same time, and it can generate and score about 1 million pairings per second on each computer, or a total of 10 million pairings per second. By "generate and score" we mean to set up one of the possible pairings of 36 golfers into 9 foursomes and then ask if it is better than the best one we found so far in terms of how it relates to the pairings of all the previous rounds. Let's say that we're really stupid and someone smarter than us could do 100 billion per second on 10 computers for a total of 1 trillion per second, or could lash together 1 million computers (to work on this very important problem). In either case we're now cranking through 1 trillion pairings per second. If we can generate and score 1 trillion pairings per second, then we could get through all possible pairings (3.73 times ten to the 23rd power) in just under a trillion seconds - 3.73 times ten to the 11th seconds, to be exact.
Sadly, there are only 31,536,000 seconds in a year (60 seconds per minute times 60 minutes per hour times 24 hours per day times 365 days per year). So 3.75 times ten to the 11th seconds divided by 31,536,000 seconds per year is 11,812 years. That's a long time to wait for pairings. And if there were 60 golfers in 15 foursomes, which is more typical of a golf league, it would take 0.4 trillion trillion million years.
That is why it's a hard problem. And yet, consider our Twin Peaks league. In that 15th round, we were able to find a pairing so that every golfer had a perfect pairing - every golfer over the 15 rounds plays with 25 golfers once and ten golfer twice. We found a perfect pairing after looking at just 173 million possible pairings in 16 seconds, which is bit less than 11,812 years. We were able to process a bit more than 10 million pairings per second for 16 seconds, and then realized that we had a "perfect pairing"
If you got through this article without fainting, you too are a geek. If you are a geek and have an index less than 10, then you are a unique geek (also called a uneek geek).
How We Solve the Problem
There are many problems that have this sort of "combinatorial explosion" as we geeks call it. These are problems that are very easy to solve when "n" is small but grow exponentially in difficulty as n gets to even 10 or 20. At some point , "brute force" - looking at all possible cases - is not possible in a reasonable period of time. Think about the Fed Ex truck coming to pick up your clubs. The driver has to make 50 stops in an area with perhaps a 50 mile radius. How does he order his stops for the day and then get back to the depot? This is a classic problem in mathematical programming, and is called the "traveling salesman problem" - start at point A, make a bunch of stops and get back to point A, ordering the stops to minimize distance traveled.
There are well developed techniques for solving these sorts of problems, and the techniques are called linear programming, dynamic programming, integer programming, quadratic programming, etc. The goal is to minimize or maximize something, subject to some constraints or rules. They are all designed to "jump in" to a very, very large "search space" and navigate around in a way that moves you to better and better solutions. The golf scheduling problem can be set-up as an integer programming problem. In fact, that is where we started in 2008 to solve this problem. Even the best packages for traditional integer programming were far, far too slow to find a solution for even 24 golfers playing 6 rounds of golf within a few second or even a few minutes. So, we developed our own very fast algorithm for solving this specific type of integer programming problem, and have refined the approach over the past 4 years.
Our founder, Dr. Michael Zisman, has a Ph.D. in this area from the Wharton School at the University of Pennsylvania, so he was able to see that the golf scheduling problem could be attacked with mathematical programming techniques. He also has 40 years of experience in IT, so he could see how we could lash together a bunch of computers to make things really, really fast. He's a geek, but with a 15 index, he's not a uneek geek.