41546
2013
2013
eng
783
798
16
594
postprint
1
2019-02-12
2019-02-12
--
Answer set programming as a modeling language for course timetabling
The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.
Postprints der Universität Potsdam : Mathematisch Naturwissenschaftliche Reihe
10.25932/publishup-41546
urn:nbn:de:kobv:517-opus4-415469
1866-8372
online registration
Theory and Practice of Logic Programming 13 (2013) 4-5, pp.783–798 DOI 10.1017/S1471068413000495
<a href="http://publishup.uni-potsdam.de/frontdoor/index/index/docId/34884">Bibliographieeintrag der Originalveröffentlichung/Quelle</a>
Keine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht
Mutsunori Banbara
Takehide Soh
Naoyuki Tamura
Katsumi Inoue
Torsten Schaub
Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
594
eng
uncontrolled
answer set programming
eng
uncontrolled
educational timetabling
eng
uncontrolled
course timetabling
Datenverarbeitung; Informatik
open_access
Mathematisch-Naturwissenschaftliche Fakultät
Referiert
Open Access
Cambridge University Press (CUP)
Universität Potsdam
https://publishup.uni-potsdam.de/files/41546/pmnr594.pdf
34884
2013
2013
eng
783
798
16
2
13
article
Cambridge Univ. Press
New York
1
--
--
--
Answer set programming as a modeling language for course timetabling
The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.
Theory and practice of logic programming
10.1017/S1471068413000495
1471-0684 (print)
wos:2011-2013
WOS:000324926400022
Banbara, M (reprint author), Kobe Univ, Nada Ku, 1-1 Rokko Dai, Kobe, Hyogo 6578501, Japan., banbara@kobe-u.ac.jp; soh@lion.kobe-u.ac.jp; tamura@kobe-u.ac.jp; inoue@nii.ac.jp; torsten@cs.uni-potsdam.de
JSPS KAKENHI [24300007]; DFG [SCHA 550/9-1]
<a href="http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-415469">Zweitveröffentlichung in der Schriftenreihe Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe ; 594</a>
Mutsunori Banbara
Takehide Soh
Naoyuki Tamura
Katsumi Inoue
Torsten Schaub
eng
uncontrolled
answer set programming
eng
uncontrolled
educational timetabling
eng
uncontrolled
course timetabling
Institut für Informatik und Computational Science
Referiert
Institut für Informatik