Bringing answer set programming to the next level: A real case on modeling course timetabling

The course timetabling problem can be defined as the task of assigning a number of lectures into a limited set of time slots and rooms, subject to a set of given constraints. The potential of Answer Set Programming (ASP), an extension of logic programming, t declaratively model course timetabling problems has been exhibited in the international course timetabling competition. Within ASP, a problem is expressed as a logic program and the solutions to the problem are obtained from the semantics of the logic program, viz., the stable models of the program. In this paper, ASP is employed to encode the course timetabling problem of the Faculty of Computer Science, Universitas Indonesia, aiming at satisfying hard constraints and minimizing the penalty incurred due to the violation of soft constraints. We identify hard constraints from this real world problem that have not been considered in the existing ASP approach, and we show how they are expressed in ASP. Our experiments using the state-of-The-Art ASP solver clingo show that several alternatives of optimal course timetables are successfully delivered while satisfying all hard constraints in an encouraging execution time. We also provide a lightweight application with a graphical user interface and clingo as the back-end, that automatically pre-processes an instance specification into clingo syntax, computes and post-processes its solutions into a tabular form.