Modifications to the Problem Description of ``Scheduling a Major College Basketball Conference'' by Nemhauser and Trick

By Michael Trick, Carnegie Mellon University
May 9, 1998
Modified July 13, 2010 to update location

The following are clarifications/modifications to better allow the exact duplication of the phases in the work by Nemhauser and Trick[1]. While the effect of these on the algorithm is minimal, these are needed in order to exactly duplicate the work in the paper. This note can be refered to as either a ``personal communication'' or by its web address http://mat.tepper.cmu.edu/trick/acc_mod.html

  1. Every team must have an H in the first three slots. ABA is not liked, and is particularly bad at the beginning. Since the ACC was rejecting all such schedules, we removed the patterns completely.
  2. Every team must have an H in the last three slots. As above.
  3. The team with the bye in the first slot must be Wake, and must end AH. The ACC fixed Wake with the bye in the first slot, and the ending is then forced.
  4. Note that Duke must have a bye in the second last weekend, so such patterns are known to end with H.
  5. The code used allowed three home weekends away in a row. Schedules having that were removed in phase 3.
This gives the complete pattern set. In the following, a -1 represents a home game and a 1 represents an away game. A 0 is a bye. Each row represents a feasible pattern.

  1 -1 -1  1 -1 -1  1 -1  1  0 -1  1 -1  1  1 -1  0  1
 -1  0  1 -1  1 -1 -1  1  0  1 -1 -1  1 -1  1  1 -1  1
 -1  1 -1 -1  1 -1  1  1 -1  0 -1  1  1 -1  1 -1  0  1
  1 -1  1 -1  0  1 -1 -1  1  1 -1 -1  1  0 -1  1 -1  1
  1 -1  0 -1  1  1 -1 -1  1  1 -1  0  1 -1 -1  1 -1  1
 -1  1 -1  1  1 -1  1  1 -1 -1  0  1 -1 -1  1 -1  1  0
  1  1 -1  1  1 -1  1 -1 -1  0 -1  1 -1 -1  1 -1  0  1
  1 -1  0  1 -1 -1  1 -1  1  1 -1  0 -1  1  1 -1 -1  1
 -1  1  1 -1  0 -1  1  1 -1  1 -1 -1  1  0  1 -1 -1  1
  1 -1 -1  1  0 -1  1 -1  1  1 -1  1 -1  0  1 -1 -1  1
  1 -1 -1  1 -1  1  1 -1  1 -1  0  1 -1  1 -1 -1  1  0
 -1  1  0 -1  1 -1  1  1 -1  1 -1  0  1 -1  1 -1 -1  1
  1  1 -1  0  1 -1  1 -1 -1  1 -1  1  0 -1  1 -1 -1  1
  1  0 -1  1  1 -1  1 -1  0  1 -1  1 -1 -1  1 -1 -1  1
  1  1 -1 -1  1  0  1 -1 -1  1 -1  1  1 -1  0 -1 -1  1
 -1  0  1 -1 -1  1 -1  1  0 -1  1 -1  1  1 -1  1  1 -1
 -1 -1  1  0 -1  1 -1  1  1 -1  1 -1  0  1 -1  1  1 -1
  1 -1  0  1 -1  1 -1 -1  1 -1  1  0 -1  1 -1  1  1 -1
  0 -1  1  1 -1  1 -1  0  1 -1  1 -1 -1  1 -1  1  1 -1
 -1  1  1 -1  0  1 -1  1 -1 -1  1 -1  1  0 -1  1  1 -1
 -1  1  1 -1  1 -1 -1  1 -1  1  0 -1  1 -1  1  1 -1  0
  1 -1 -1  1  0  1 -1 -1  1 -1  1  1 -1  0 -1  1  1 -1
 -1  1  0 -1  1  1 -1  1 -1 -1  1  0  1 -1 -1  1  1 -1
 -1  1 -1  1  1 -1  0  1 -1 -1  1  1 -1 -1  1  0  1 -1
 -1  0 -1  1 -1 -1  1  1  0 -1  1  1 -1  1  1 -1  1 -1
  0  1 -1  1 -1 -1  1  0 -1 -1  1  1 -1  1  1 -1  1 -1
  1 -1  1 -1 -1  1 -1 -1  1  1  0 -1  1  1 -1  1 -1  0
 -1  1  0  1 -1 -1  1  1 -1 -1  1  0 -1  1  1 -1  1 -1
 -1  1  1 -1 -1  1  0  1 -1 -1  1 -1  1  1 -1  0  1 -1
  1 -1 -1  1 -1  1  0 -1  1 -1  1  1 -1  1 -1  0  1 -1
 -1  1 -1  1  0 -1  1  1 -1 -1  1  1 -1  0  1 -1  1 -1
  1 -1  1  1 -1  1 -1 -1  1  0  1 -1 -1  1 -1  1  0 -1
  1  0 -1  1 -1  1  1 -1  0 -1  1  1 -1  1 -1 -1  1 -1
 -1  1  1 -1  1  1 -1  1 -1  0  1 -1  1 -1 -1  1  0 -1
  1  1 -1  1 -1 -1  1 -1 -1  0  1  1 -1  1  1 -1  0 -1
 -1  1  1 -1  1  0 -1  1 -1  1  1 -1  1 -1  0  1 -1 -1
 -1  1 -1  1  1 -1  1  1 -1  0  1  1 -1 -1  1 -1  0 -1
  1  1 -1  1  1 -1  1 -1 -1  1  0  1 -1 -1  1 -1 -1  0
Additional Notes: The formulation for phase 1 includes constraints to preclude pattern sets for which there are no timetables. In particular, if, for a pair of patterns, there does not exist a slot where one team has a +1 and the other a -1 (and another where the reverse holds), then the teams cannot play against each other. Therefore a constraint allowing only one of the pair in the pattern set is added. This sharply decreases the number of pattern sets.

I would like to thank Irv Lustig of ILOG CPLEX Division for working with me to duplicate our work and identifying these issues (problems with exactly duplicating our work had been noted by Martin Henz).