{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T06:07:24Z","timestamp":1761977244313,"version":"build-2065373602"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T00:00:00Z","timestamp":1380067200000},"content-version":"unspecified","delay-in-days":86,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>S<\/jats:italic> is expressed by rules in which the head is the form of <jats:monospace>penalty<\/jats:monospace>(<jats:italic>S<\/jats:italic>,<jats:italic>V<\/jats:italic>,<jats:italic>C<\/jats:italic>), and a violation <jats:italic>V<\/jats:italic> and its penalty cost <jats:italic>C<\/jats:italic> 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.<\/jats:p>","DOI":"10.1017\/s1471068413000495","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T16:24:58Z","timestamp":1380126298000},"page":"783-798","source":"Crossref","is-referenced-by-count":14,"title":["Answer set programming as a modeling language for course timetabling"],"prefix":"10.1017","volume":"13","author":[{"given":"MUTSUNORI","family":"BANBARA","sequence":"first","affiliation":[]},{"given":"TAKEHIDE","family":"SOH","sequence":"additional","affiliation":[]},{"given":"NAOYUKI","family":"TAMURA","sequence":"additional","affiliation":[]},{"given":"KATSUMI","family":"INOUE","sequence":"additional","affiliation":[]},{"given":"TORSTEN","family":"SCHAUB","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,9,25]]},"reference":[{"key":"S1471068413000495_ref24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068413000495_ref23","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0320"},{"key":"S1471068413000495_ref22","first-page":"3","volume-title":"Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006), Revised Selected Papers","author":"McCollum","year":"2007"},{"key":"S1471068413000495_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-007-0097-0"},{"key":"S1471068413000495_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0700-7"},{"key":"S1471068413000495_ref19","first-page":"73","volume-title":"Proceedings of IFIP Congress 62","author":"Gotlieb","year":"1962"},{"key":"S1471068413000495_ref18","first-page":"1070","volume-title":"Proceedings of the Fifth International Conference and Symposium on Logic Programming","author":"Gelfond","year":"1988"},{"key":"S1471068413000495_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04238-6_50"},{"key":"S1471068413000495_ref16","first-page":"386","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007)","author":"Gebser","year":"2007"},{"key":"S1471068413000495_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20895-9_40"},{"key":"S1471068413000495_ref12","unstructured":"Gaspero L. D. , McCollum B. and Schaerf A. 2007. The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3). Technical report, Queen's University, Belfast, United Kingdom. URL: http:\/\/www.cs.qub.ac.uk\/itc2007\/curriculmcourse\/report\/curriculumtechreport.pdf."},{"key":"S1471068413000495_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0716-z"},{"key":"S1471068413000495_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.02.023"},{"key":"S1471068413000495_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0707-0"},{"key":"S1471068413000495_ref26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006576209967"},{"key":"S1471068413000495_ref2","first-page":"211","volume-title":"Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)","author":"Andres","year":"2012"},{"key":"S1471068413000495_ref1","unstructured":"Ach\u00e1 R. A. and Nieuwenhuis R. 2012. Curriculum-based course timetabling with SAT and MaxSAT. Annals of Operations Research (February 2012), 1\u201321."},{"key":"S1471068413000495_ref11","first-page":"43","volume-title":"Proceedings of the 13th Workshop on Logic Programming (WLP'98)","author":"Faber","year":"1998"},{"key":"S1471068413000495_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-010-9103-2"},{"key":"S1471068413000495_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0828-5"},{"key":"S1471068413000495_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00069-3"},{"key":"S1471068413000495_ref13","first-page":"262","volume-title":"Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2002)","author":"Gaspero","year":"2003"},{"key":"S1471068413000495_ref14","doi-asserted-by":"crossref","DOI":"10.2200\/S00457ED1V01Y201211AIM019","volume-title":"Answer Set Solving in Practice","author":"Gebser","year":"2012"},{"key":"S1471068413000495_ref25","first-page":"161","volume-title":"Proceedings of the 5th international conference on the practice and theory of automated timetabling (PATAT 2004)","author":"Qualizza","year":"2005"},{"key":"S1471068413000495_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-006-0074-z"},{"key":"S1471068413000495_ref9","first-page":"64","volume-title":"Proceedings of the 3th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2000)","author":"Carter","year":"2001"},{"key":"S1471068413000495_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.06.023"},{"key":"S1471068413000495_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543357"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068413000495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T09:29:16Z","timestamp":1715592556000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068413000495\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":28,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S1471068413000495"],"URL":"https:\/\/doi.org\/10.1017\/s1471068413000495","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2013,7]]}}}