Dr. Dobb's Journal February 1997
The term "NP-complete" refers to a family of problems that are all roughly equivalent; if you could find a fast algorithm to solve one of these problems, the others would quickly follow. NP-complete problems are both extremely common and frustratingly difficult. Many problems of the form "find the best/cheapest/shortest way to do X" are NP-complete, and a fast solution to NP-complete problems would revolutionize such disparate fields as compiler optimization and airline scheduling. However, in lieu of such a breakthrough, the best way to deal with an NP-complete problem is usually to find a trick that will give you a "good enough" approximate solution. This month, Oleg discusses an NP-complete problem that he encountered in trying to schedule a chess tournament, and the approximate solution that made it feasible.
-- Tim Kientzle
Many years ago, when I was still a chemist, I was approached by a scientist of the "old school" who didn't like computers. To my surprise, he asked me for help in using computers to schedule a traditional New Year "blitz" chess tournament. That year, quite a few participants were expected, prompting a switch to a Swiss system. In this method of conducting a tournament, the total number of games to be played is specified in advance and is smaller than n
(n-1)/2, where n is the number of participants. Consequently, not everybody would end up playing with everybody. To be fair, the scheduler would have to match partners of equal skill, provided they hadn't played already. Keeping track of who played whom and (at the same time) trying to find partners of similar strength would quickly become a pain. That's why he thought a computer might be of some help.
In the actual setting, there were about 20 participants, and 10 rounds were played. In each round, partners played two five-minute games (one person plays white, another black, then they switch). So, one can score 0 (lost both games), 1/2 (lost one, tied the other), and so on up to 2 points (won both). After a round was over, the results were entered into a computer that had to come up with the pairings for the next round. The players scheduled in the next round must not have played each other in previous rounds; moreover, their scores should be as close as possible.
For example, consider the tournament in Table 1: Eight people who have already played three rounds. In the first round of the tournament, there are no constraints: No one has played a game, and everyone has the same score (zero). Consequently, any schedule will do; for example, player 2i-1 plays against player 2i, with the numbers being assigned randomly. After the round is played, a few leaders emerge. They're pitted against each other in the next round, and so on. After the third round, the leaders are #1 and #5, but they've already played each other. Aiming to match scores as closely as possible, you could pair players #1-#4, #5-#7, and #3-#8. This leaves #6 and #2, but they have already played! You can see the kind of conflicts you have to resolve. With 20 players, the situation becomes very tangled very quickly.
You can think about the scheduling problem in terms of graphs. Consider a graph where each vertex represents a potential pair. For example, vertex 1-2 represents a pairing of players #1 and #2. Initially there are n(n-1)/2 vertices where n is the number of players. As the tournament progresses, you remove vertices that have already played. Two vertices are connected if the two pairs can both appear in the same round; for example, vertices 1-2 and 1-3 are not connected, since player #1 can't play player #2 and player #3 at the same time. Vertices 1-2 and 3-4 are connected. There is a cost associated with each vertex: a disparity of scores of the two players. This cost is updated after each round. Figure 1, for example, shows the graph corresponding to the situation after the third round in our sample tournament. The scheduling problem is reduced to finding a clique of a minimal cost in the graph. That is, find a set of n/2 vertices that are all connected with each other (a clique of order n/2) such that the total cost (of all vertices in the clique) is minimal. It is obvious that a clique of order n/2 means that all n participants will play in the round.
Finding a clique in a graph is, by itself, an NP-complete problem. But it pales in comparison with the requirement of finding a clique of minimal cost. A naive solution would be to consider all possible subsets of n/2 vertices of the graph, check to see if they all are connected with each other, compute the total cost, and pick up a subset with the minimal cost. The complexity of this obvious solution is far more than exponential in n. For example, in a tournament with 20 participants, you have to choose 10 pairs from 190 possible pairs. There are over 1016 possible combinations to consider, a formidable number for even the most powerful supercomputer.
Even if you want the exact optimal solution, however, you can do better than this. Assume for a moment that player #1 has stepped out, and we have to schedule a round without him. Obviously, some other player has to take the round off, too. Suppose that for each i=2..n, you have come up with optimal schedules involving all players but i and 1. In graph terms, you found optimal cliques of order (n/2)-1 that don't contain vertices mentioning 1 and i. The cost of that clique would be cost(all-{1,i}). Suppose player #1 has shown up and wants to play the round after all. Rather than rebuilding the schedule from scratch, you can use the already-found partial optimal schedules, add players #1 and i to them, and select the one with the smallest total cost. For each player i, the total cost is cost(all) = cost(all-{1,i}) + cost({1,i}), where cost({1,i}) is the disparity in scores between players i and #1. If players i and #1 have already played, put cost({1,i}) to infinity.
This technique is easy to justify: If the optimal schedule matches player #1 against player i, then the schedule without these players also has to be optimal (with respect to the remaining players). Otherwise, you can lower the cost of the original schedule, which would contradict the premise that it is optimal. To find the best partial schedules, you can repeat this algorithm recursively. This dynamical programming algorithm -- similar to the one used to solve the traveling-salesman problem (TSP) -- reduces the complexity somewhat, to the order of (n-1)2n-1. The origin of this estimate is easy to see: You need to consider all even subsets of the set of all players. Determining an optimal schedule for a subset (given optimal schedules for smaller subsets computed previously) takes no more than (n-1) operations: adding a cost of a new pair and selecting the smallest term. For n=20 players, it should take no more than 107 operations to schedule a round, immensely faster than the aforementioned naive algorithm.
However, this algorithm is fast because it caches the partial schedules. This cache is quite large, several megabytes for n=20. At the time, I only had a lowly PDP-11 to work with, so I wasn't able to use even this improved algorithm.
In practice, you do not need the perfect schedule -- a reasonably good approximation suffices. To speed things up, I used a simpler approach. I first sorted all players by their scores, then tried to pick partners that were neighbors in this sorted list. I started with the player at the top of the list, and walked down the list, picking the first available partner, providing they hadn't played already. Then I'd pick the player with the next-highest score (if still available) and find him a partner, and so on. Since the list is sorted, picking close players from this list gives pairs with similar scores.
This greedy strategy of scheduling by adding pairs of players with the closest score may not necessarily lead to the lowest overall cost. For example, after picking all but one pair, you have no choice for the final pair. It may happen that their scores are so different that the total cost is enormous. Worse, this last pair may have already played: Then the entire schedule crumbles. If this is the case, you can back off and try changing the arrangement for the next-to-last pair, hoping that the last pair would be suitable this time. Although building the complete schedule this way may not be optimal, it is close.
Note that the list of players is sorted in descending order, and I start pairing from the top. Most of the backtracking and fiddling is then done with the players near the bottom of the list. That is, even if the final solution may not be optimal as a whole, you err by mismatching losers rather than leaders. The possible inaccuracy pays off handsomely in terms of complexity: It takes only n(n-1)/2 operations to go through the entire list and arrange pairs. Backtracking adds to the complexity, and this could be significant; however, in reality, the convergence is fast. The memory requirements are bounded and small.
Once the schedule is complete, I evaluate its total cost (called measure in the code, available electronically; see "Availability," page 3). Then I backtrack once again, trying to find another complete schedule. I repeat this process up to five times, and pick the schedule with the smallest cost. Although the algorithm is based on a greedy strategy, it still tries to find a global optimum. The whole idea is similar to that of approximate TSP algorithms, even though at the time I only had a very vague understanding of TSP.
This fast algorithm was used to schedule the tournament in real time. That is, after a round was finished, the results were entered into the computer. It had to come up with a schedule for the new round while the participants were taking a break. The cumulative tournament results (history) were kept in a matrix Has_played and a vector Scores, with obvious meaning. The code had provisions to save/restore this history in a file, a precaution against the event of a power surge during the tournament (it happened a few times). Note that the players are numbered 1 through n (so index 0 has a special meaning). A schedule is represented by a vector allo: allo[i], if not zero, tells who player i is to play with; zero allo[i] means that player i is available for allocation. The first step of scheduling is sorting the list of players according to their scores in array Sorted_indices, so that Scores[Sorted_indices[i]] >= Scores[Sorted_indices[j]] for all i>j. The rest of the algorithm can be written as in Example 1.
Function try_allocate() (also available electronically) follows this idea almost literally, with the exception that it is not recursive. The first version of the code was written in DEC Basic on the PDP-11, which doesn't support recursion. Even when I later rewrote the program in C, I stuck with the faster iterative approach.
The only variables that define an arrangement of a pair are the indices i and j of the players in the sorted list. You can keep these indices for each arranged pair in special arrays, si and sj, accessed through an index level. This makes it easy to back off the arrangement to the previous level(s). The scheduling process is made of a series of actions: Pick up a suitable i, pick up j, arrange the next pair (that is, advance the "level"), or back off and try the next j; after that, try the next i. The action to execute depends on the previous action and some tests (availability of players). This is exactly how a finite automaton runs. The scheduler function in the listing implements this automaton literally.
The C compiler I initially used was pre-ANSI C. I have recently beautified the code, mainly adding void. The code runs, and even the user interface for a VT100 terminal works. The program had been used for several years and, I think, helped convince my professor that computers aren't all evil.
DDJ