Using integer programming and constraint programming to solve sports scheduling problems

The integration of integer programming (IP) and constraint programming (CP) is a topic that has received much interest and attention in recent years. One of the fundamental goals of this research is to advance the current state of knowledge regarding aggregate IP-CP techniques. To this end, three sports scheduling problems are examined.; The Traveling Tournament Problem (TTP) represents the fundamental issues involved in creating a schedule for sports leagues where the amount of team travel is an issue. The solution methodology presented here is a parallel branch-and-price algorithm that uses IP to solve the master problem and CP to solve the pricing problem. Additionally, constraint programming is used as a primal heuristic.; The Atlantic Coast Conference (ACC) Problem is the actual scheduling problem solved each year to determine the double round robin tournament schedule played during the regular season by the nine Division I basketball teams in the ACC. Prior to this research, the Non-mirrored ACC Problem was unsolved. The solution methodology developed here is an adaptation of the combined IP-CP approach used to solve the TTP.; The Colonial Athletic Association (CAA) Problem is also an actual scheduling problem used to determine the double round robin tournament schedule played during the regular season by the nine Division I basketball teams in the Colonial Athletic Association. This research includes a methodology for solving the CAA Problem that uses higher order branching techniques originated by the mathematical programming community within a constraint programming framework.; The goals of this research are threefold: to solve three previously unsolved sports scheduling problems and set forth a general guideline for approaching practical tournament problems, to provide a framework for combining integer programming and constraint programming techniques, and to identify a problem class that can be successfully solved using an aggregate approach and that might serve as a basis for future research on techniques that integrate IP and CP.