|
FriarTuck, A Constraint-Based Tournament-Scheduling Tool
In round-robin sports competitions, each team plays each other once (single roundrobin) or
twice (double round-robin). Tournament planners can easily schedule
standardround-robin tournaments because there are known algorithms,
published tournament schedules, and readily available software. However,
with additional constraints, round-robin planning quickly degenerates
into a combinatorial search problem, and additional constraints abound
in professional sports: team commitments, fan preferences, TV station
requirements, and so forth. FriarTuck, a constraint-based roundrobin
scheduling tool, lets tournament coordinators enter a variety of
constraints to compute optimal solutions to complex tournament-planning
problems.
A constraint-based approach
George Nemhauser and
Michael Trick studied an extreme case involving constraints, the 1997/98
Atlantic Coast Conference in basketball. The ACC includes nine
universities, and its basketball program runs an annual
double-round-robin tournament. Various constraints limit the possible
sequences of home and away matches, assign matches between given teams
to particular dates, force teams to play at home (or away) on particular
dates, restrict teams from playing against strong teams twice in a row,
and so on. Nemhauser and Trick used integer programming and exhaustive
enumeration to create schedules that fulfill all constraints. I have
found that constraint programming offers significant advantages for
modeling and solving round-robin tournament problems and outperforms
these operations research techniques on the ACC problem. Usually,
round-robin tournament planning is decomposed into three successive
phases: finding patterns, generating pattern sets, and developing
schedules. Constraint programming can employ symbolic constraints such
as all different and element for all three phases. The
constraints propagate information in the nodes of the search tree, guide
the search, and prune the tree. A constraint-based tree search often
finds solutions to tournament-scheduling problems quickly. For example,
a state-of-the-art constraint programming system can find all 179
solutions to the ACC problem in one minute on a PC, as opposed to the
24-hour computing time reported by Nemhauser and Trick.
FriarTuck
FriarTuck provides
users with a variety of constraint editors for round-robin tournaments.
These editors are expressive enough to formulate the full ACC problem
and various other constraints. Users can choose to automatically
sequence the solution phases or manually explore the possibilities in
each phase. FriarTuck generates and displays schedules and saves them
in HTML format. The figure shows the constraint editor for fixing
patterns and opponents, the interface to the solver phases, and the
display of a generated schedule. I implemented FriarTuck in the
concurrent constraint language Oz, which combines finite-domain
constraint programing with a rich language for symbolic processing.
I used the programming
system Mozart, which supports the development of advanced applications
through innovative constraint programming tools and extensive support
for distributed computing. (Mozart was developed by the Mozart
Consortium, which includes the Programming Systems Lab, Saarbrüken;
Swedish Institute of Computer Science, Stockholm; and Universitä
Catholique de Louvain. For more information, visit www.mozart-oz.org.)
Events coordinators have used FriarTuck to schedule sports tournaments
in England and the US in 1999 and 2000, including
- The West of England Club Cricket Championship, which has 71
cricket clubs, totaling 142 teams;
- The Wisconsin Intercollegiate Athletic Conference, several leagues
in men's and women's basketball, with nine teams per league;
- The Colonial Athletic Conference, a basketball camp with over 50
teams playing round-robin tournaments in several different leagues;
- The Bill George Youth Football League, consisting of 130 teams and
496 games; and
- A euchre tournament, a card game with various two-player teams.
Tightly constrained round-robin tournaments are showcase applications of
constraint programming. To tackle large irregular tournaments that
currently lie beyond the capabilities of FriarTuck, round-robinspecific
constraint-propagation algorithms will become important.
References
- G L. Nemhauser and M.A. Trick, Scheduling a Major College
Basketball Conference, Operations Research,Vol. 46, No. 1,
1998, pp. 1-8.
- M. Henz, Constraint-Based Round Robin Tournament Planning, Proc.
Int'l Conf. Logic Programming, MIT Press, Cambridge, Mass.,
1999, pp. 545-557.
- M. Henz, Scheduling a Major College Basketball
Conference-Revisited, to be published in Operations Research,
2000.
- G. Smolka, The Oz Programming Model, Computer Science Today,
Lecture Notes in
IEEE
Intelligent Systems
Copyright © 2001 Singapore Press Holdings
Date: January / February 2000
|