Integer Programming versus Constraint Programming: A Course Timetabling Case Study - Gulcu, Ayla; Bulkan, Serol (International Journal of Industrial Engineering: Theory, Applications and Practice, 2019)
In this article, two solution approaches are compared for a real-world, moderate-size but a highly constrained university course timetabling problem. The first approach is developing an integer programming model, and solving it by using a commercial solver. The model proposes new formulations for the constraints that are hard to formulate. The second approach is developing a constraint programming heuristic, and implementing it by a programming language and solving the problem by this heuristic. The heuristic employs a backtracking mechanism inspired from tabu search which was found to be very helpful in identifying the inconsistencies in the input data. Indeed, it was initially developed to identify the courses that prevent feasible timetables from being produced. In order to be able to show the performance of this heuristic, we tested it on different instances of a well-known course timetabling problem, ITC-2007 datasets. A performance comparison of the two methods in terms of both solution quality and computational time is presented for the real-world problem. Different constraint configurations of the problem has been created and the two solution methods have also been compared under different constraint configurations. It has been observed that the relative performances of the two methods significantly differ under various constraint configurations.