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

Irvi Firqotul Aini, Ari Saptawijaya, Siti Aminah

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2017 International Conference on Advanced Computer Science and Information Systems, ICACSIS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages471-476
Number of pages6
ISBN (Electronic)9781538631720
DOIs
Publication statusPublished - 2 Jul 2017
Event9th International Conference on Advanced Computer Science and Information Systems, ICACSIS 2017 - Jakarta, Indonesia
Duration: 28 Oct 201729 Oct 2017

Publication series

Name2017 International Conference on Advanced Computer Science and Information Systems, ICACSIS 2017
Volume2018-January

Conference

Conference9th International Conference on Advanced Computer Science and Information Systems, ICACSIS 2017
Country/TerritoryIndonesia
CityJakarta
Period28/10/1729/10/17

Fingerprint

Dive into the research topics of 'Bringing answer set programming to the next level: A real case on modeling course timetabling'. Together they form a unique fingerprint.

Cite this