Kathryn Pedings, College of Charleston


Minimum Violations Sports Ranking Using Binary Integer Linear Program and Evolutionary Optimization Approaches

Abstract: Every March, the exercise of ranking sports teams becomes the center of attention as basketball fanatics prepare for the NCAA basketball playoffs. People everywhere fill out tournament brackets in hopes of making correct predictions on the outcomes of the games. Our research group develops algorithms to rank sports teams with data from the regular season play to fill in these brackets using mathematical ideas. We define a special form of a matrix called hillside form that describes a perfect season of game play and our algorithms minimize the number of violations to this form for some given data matrix. We formulated two algorithms to find the ranking that symmetrically reorders the matrix so that the resulting array has the minimum violations to hillside form. Our problem can be formulated as a binary integer linear program (BILP) that solves this problem to optimality. The down side of our BILP is that it requires industrial optimization software for large problems, and some problems can’t even be solved with this special software. We attempt to solve these issues using evolutionary optimization (EO). EO algorithms have been used for decades to obtain heuristic solutions to intractable, real-world problems. EO uses Darwinian ideas of mating, mutating, fitness, and survival of the fittest to determine the best solution to the ranking problem. We have submitted brackets from these two algorithms for the past two years in the ESPN NCAA March Madness Challenge.

Collaborators: Dr. Amy Lanville (College of Charleston), Dr. Yoshitsugu Yamamoto (University of Tsukuba, Japan), Dr. Tim Chartier (Davidson College), Erich Kreutzer (Davidson College).