Integer Programming versus Constraint Programming: A Course Timetabling Case Study

Authors

DOI:

https://doi.org/10.23055/ijietap.2019.26.3.3624

Keywords:

Course timetabling, integer programming, constraint programming

Abstract

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.

Author Biographies

Ayla Gulcu, Fatih Sultan Mehmet Vakif University

Computer Engineering

Serol Bulkan, Marmara University

Industrial Engineering

Published

2019-07-20

How to Cite

Gulcu, A., & Bulkan, S. (2019). Integer Programming versus Constraint Programming: A Course Timetabling Case Study. International Journal of Industrial Engineering: Theory, Applications and Practice, 26(3). https://doi.org/10.23055/ijietap.2019.26.3.3624

Issue

Section

Operations Research