Open Collections

Scheduling the sports of Canada West : a tale of two discrete optimization models

University of British Columbia

Mixed Integer Programming (MIP) and Constraint Programming (CP) are two of the most influential discrete optimization strategies available to practitioners. They can be applied to many of the same problems, yet they operate on two very different paradigms. MIP relies on the convexity of a collection of linear inequalities while CP employs global constraints while processing the search space. This thesis provides a thorough description of implementing a generic sports scheduling model using both MIP and CP. The goal is to clearly contrast the implementation of the model in the two strategies. The strategies are then analyzed with performance profiles based on real sports scheduling problems. Modeling real world problems requires a deep understanding of the structure of the problem. Exploiting the structure of a particular problem is key to modeling discrete optimization problems effectively. We demonstrate this idea by testing a constraint that exploits an implicit structure of sports leagues schedule.

Text

2020-10-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/76376

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/