[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

\({\varvec{teaspoon}}\): solving the curriculum-based course timetabling problems with answer set programming

  • S.I.: PATAT 2016
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Answer Set Programming (ASP) is an approach to declarative problem solving, combining a rich yet simple modeling language with high performance solving capacities. We here develop an ASP-based approach to curriculum-based course timetabling (CB-CTT), one of the most widely studied course timetabling problems. The resulting teaspoon system reads a CB-CTT instance of a standard input format and converts it into a set of ASP facts. In turn, these facts are combined with a first-order encoding for CB-CTT solving, which can subsequently be solved by any off-the-shelf ASP systems. We establish the competitiveness of our approach by empirically contrasting it to the best known bounds obtained so far via dedicated implementations. Furthermore, we extend the teaspoon system to multi-objective course timetabling and consider minimal perturbation problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. http://tabu.diegm.uniud.it/ctt/.

  2. As of July 20, 2017.

  3. Care must be taken whenever such expressions are evaluated during solving (rather than grounding).

  4. Syntactically, each \(\mathtt {w_j}\) can be an arbitrary term. In fact, often tuples are used rather than singular weights to ensure a multi-set property; in such a case the summation only applies to the first element of selected tuples.

  5. teaspoon: TimEtabling with Answer Set PrOgrammiNg.

  6. Surprisingly, the teaspoon system was able to find an optimal solution of

    figure i

    in this formulation.

  7. We used revision r10140 of the current development branch available at https://potassco.org/.

  8. We are aware that the training set is included in the test set. The decision was made since no separate instance set was available and we wanted to record results for all instances and configurations.

  9. http://www.cs.qub.ac.uk/itc2007/index_files/ordering.htm.

  10. As mentioned, modern ASP systems like clingo first translate logic programs (with variables) into equivalent ground (that is, variable-free) programs, and then compute the answer sets of the ground programs. The former is called grounding, and the latter is called solving.

  11. Among the six instances of erlangen, erlangen2011_2, erlangen2012_1, erlangen2012_2, and erlangen2013_1 have been changed since 2014 due to the crush of the CB-CTT portal. We used new version of these instances in Table 7. Note that our previous works (Banbara et al. 2013, 2016) used old ones.

  12. http://tabu.diegm.uniud.it/ctt/ as of July 20 2017.

  13. All source code is available from https://potassco.org/doc/apps/.

References

  • Abdullah, S., Turabieh, H., McCollum, B., & McMullan, P. (2012). A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics, 18(1), 1–23.

    Article  Google Scholar 

  • Achá, R. A., & Nieuwenhuis, R. (2012). Curriculum-based course timetabling with SAT and MaxSAT. Annals of Operations Research, 218, 1–21.

    Google Scholar 

  • Andres, B., Kaufmann, B., Matheis, O., & Schaub T. (2012). Unsatisfiability-based optimization in clasp. In: A. Dovier & V. Santos Costa (Eds.), Technical communications of the twenty-eighth international conference on logic programming (ICLP’12), Leibniz international proceedings in informatics (LIPIcs) (Vol. 17, pp. 212–221).

  • Ansótegui, C., Bonet, M., & Levy, J. (2013). SAT-based MaxSAT algorithms. Artificial Intelligence, 196, 77–105.

    Article  Google Scholar 

  • Banbara, M., Soh, T., Tamura, N., Inoue, K., & Schaub, T. (2013). Answer set programming as a modeling language for course timetabling. Theory and Practice of Logic Programming, 13(4–5), 783–798.

    Article  Google Scholar 

  • Banbara, M., Inoue, K., Kaufmann, B., Schaub, T., Soh, T., Tamura, N., et al. (2016). teaspoon: Solving the curriculum-based course timetabling problems with answer set programming. In: E. K. Burke, L. Di Gaspero, E. Özcan, B. McCollum, & A. Schaerf (Eds.), Proceedings of the 11th international conference on the practice and theory of automated timetabling (PATAT’16) (pp. 13–32).

  • Baral, C. (2003). Knowledge representation, reasoning and declarative problem solving. Cambridge: Cambridge University Press.

    Book  Google Scholar 

  • Barták, R., Müller, T., & Rudová, H. (2004). A new approach to modeling and solving minimal perturbation problems. In K. R. Apt, F. Fages, F. Rossi, P. Szeredi, & J. Váncza (Eds.), Recent advances in constraints, joint ERCIM/CoLogNET international workshop on constraint solving and constraint logic programming (CSCLP’03) (Vol. 3010, pp. 233–249). Springer, LNCS.

  • Bettinelli, A., Cacchiani, V., Roberti, R., & Paolo, Toth. (2015). An overview of curriculum-based course timetabling. TOP, 23(2), 313–349.

    Article  Google Scholar 

  • Biere, A., Heule, M., van Maaren, H., & Walsh, T. (Eds.). (2009). Handbook of satisfiability, frontiers in artificial intelligence and applications (Vol. 185). Clifton: IOS Press.

    Google Scholar 

  • Bonutti, A., De Cesco, F., Di Gaspero, L., & Schaerf, A. (2012). Benchmarking curriculum-based course timetabling: Formulations, data formats, instances, validation, visualization, and results. Annals of Operations Research, 194(1), 59–70.

    Article  Google Scholar 

  • Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.

    Article  Google Scholar 

  • Burke, E. K., Marecek, J., Parkes, A. J., & Rudová, H. (2010a). Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research, 37(3), 582–597.

    Article  Google Scholar 

  • Burke, E. K., Marecek, J., Parkes, A. J., & Rudová, H. (2010b). A supernodal formulation of vertex colouring with applications in course timetabling. Annals of Operations Research, 179(1), 105–130.

    Article  Google Scholar 

  • Burke, E. K., Marecek, J., Parkes, A. J., & Rudová, H. (2012). A branch-and-cut procedure for the Udine course timetabling problem. Annals of Operations Research, 194(1), 71–87.

    Article  Google Scholar 

  • Demirovic, E., & Musliu, N. (2017). MaxSAT-based large neighborhood search for high school timetabling. Computers & OR, 78, 172–180.

    Article  Google Scholar 

  • Di Gaspero, L., & Schaerf, A. (2003). Multi-neighbourhood local search with application to course timetabling. In E. K. Burke & P. D. Causmaecker (Eds.) Proceedings of the 4th international conference on the practice and theory of automated timetabling (PATAT’02) (Vol. 2740, pp. 262–275). Berlin: Springer, LNCS.

  • Di Gaspero, L., & Schaerf, A. (2006). Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modelling and Algorithms, 5(1), 65–89.

    Article  Google Scholar 

  • Di Gaspero, L., McCollum, B., & Schaerf, A. (2007). The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3). Technical report, Queen’s University, Belfast, United Kingdom

  • Eén, N., & Sörensson, N. (2003). Temporal induction by incremental SAT solving. Electronic Notes in Theoretical Computer Science, 89(4), 543–560.

    Article  Google Scholar 

  • Ehrgott, M. (2005). Multicriteria Optimization. Berlin: Springer.

    Google Scholar 

  • Erdem, E., Gelfond, M., & Leone, N. (2016). Applications of ASP. AI Magazine, 37(3), 53–68.

    Article  Google Scholar 

  • Faber, W., Leone, N., & Pfeifer, G. (1998). Representing school timetabling in a disjunctive logic programming language. In U. Egly & H. Tompits (Eds.), Proceedings of the 13th workshop on logic programming (WLP’98) (pp. 43–52).

  • Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2012). Answer set solving in practice. Synthesis lectures on artificial intelligence and machine learning. San Rafael: Morgan and Claypool Publishers.

    Google Scholar 

  • Gebser, M., Kaufmann, B., Otero, R., Romero, J., Schaub, T., & Wanko P. (2013). Domain-specific heuristics in answer set programming. In: M. desJardins & M. Littman (Eds.), Proceedings of the twenty-seventh national conference on artificial intelligence (AAAI’13) (pp. 350–356). AAAI Press.

  • Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., & Schaub, T. (2015a). Progress in clasp series 3. In F. Calimeri, G. Ianni, & M. Truszczyński (eds) Proceedings of the thirteenth international conference on logic programming and nonmonotonic reasoning (LPNMR’15) (Vol. 9345, pp. 368–383). Springe, LNAI.

  • Gebser, M., Kaminski, R., Obermeier, P., & Schaub, T. (2015b). Ricochet robots reloaded: A case-study in multi-shot ASP solving. In: T. Eiter, H. Strass, M. Truszczyński, & S. Woltran (Eds.), Advances in knowledge representation, logic programming, and abstract argumentation: Essays dedicated to Gerhard Brewka on the occasion of his 60th birthday (Vol. 9060, pp. 17–32). Springer, LNAI.

  • Geiger, M. J. (2012). Applying the threshold accepting metaheuristic to curriculum based course timetabling—A contribution to the second international timetabling competition ITC 2007. Annals of Operations Research, 194(1), 189–202.

    Article  Google Scholar 

  • Gelfond, M, & Lifschitz, V. (1988). The stable model semantics for logic programming. In Proceedings of the fifth international conference and symposium on logic programming (pp. 1070–1080). MIT Press.

  • Hutter, F., Hoos, H., & Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In Proceedings of the fifth international conference on learning and intelligent optimization (LION’11) (Vol. 6683, pp. 507–523). Springer, LNCS.

  • Lach, G., & Lübbecke, M. E. (2012). Curriculum based course timetabling: New solutions to Udine benchmark instances. Annals of Operations Research, 194(1), 255–272.

    Article  Google Scholar 

  • Lewis, R. (2007). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167–190.

    Article  Google Scholar 

  • Lü, Z., & Hao, J. K. (2010). Adaptive tabu search for course timetabling. European Journal of Operational Research, 200(1), 235–244.

    Article  Google Scholar 

  • Marler, R., & Arora, J. (2004). Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26(6), 369–395.

    Article  Google Scholar 

  • Marques-Silva, J., & Planes, J. (2007). On using unsatisfiability for solving maximum satisfiability. CoRR abs/0712.1097

  • McCollum, B. (2007). A perspective on bridging the gap between theory and practice in university timetabling. In EK Burke, & H Rudová (Eds.), Proceedings of the 6th international conference on the practice and theory of automated timetabling (PATAT’06) (Vol 3867, pp. 3–23). Revised Selected Papers, Springer, LNCS.

  • McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A. J., et al. (2010). Setting the research agenda in automated timetabling: The second international timetabling competition. INFORMS Journal on Computing, 22(1), 120–130.

    Article  Google Scholar 

  • Müller, T. (2009). ITC2007 solver description: A hybrid approach. Annals of Operations Research, 172(1), 429–446.

    Article  Google Scholar 

  • Müller, T., Rudová, H., & Barták, R. (2005). Minimal perturbation problem in course timetabling. In E. K. Burke, & M. A. Trick (Eds.), Proceedings of the 5th international conference on the practice and theory of automated timetabling (PATAT’04) (Vol. 3616, pp. 126–146). Springer, LNCS.

  • Narodytska, N., & Bacchus, F. (2014). Maximum satisfiability using core-guided MaxSAT resolution. In C. Brodley, & P. Stone (Eds.), Proceedings of the twenty-eighth national conference on artificial intelligence (AAAI’14) (pp. 2717–2723). AAAI Press

  • Niemelä, I. (1999). Logic programs with stable model semantics as a constraint programming paradigm. Ann Mathematics and Artificial Intelligence, 25(3–4), 241–273.

    Article  Google Scholar 

  • Phillips, A. E., Walker, C. G., Ehrgott, M., & Ryan, D. M. (2016). Integer programming for minimal perturbation problems in university course timetabling. Annals of Operations Research, 252, 1–22.

    Google Scholar 

  • Rudová, H., Müller, T., & Murray, K. S. (2011). Complex university course timetabling. Journal of Scheduling, 14(2), 187–207.

    Article  Google Scholar 

  • Sakkout, H. E., & Wallace, M. (2000). Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 4(5), 359–388.

    Article  Google Scholar 

  • Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127.

    Article  Google Scholar 

  • Schwind, N., Okimoto, T., Konieczny, S., Wack, M., & Inoue, K. (2014). Utilitarian and egalitarian solutions for multi-objective constraint optimization. In Proceedings of the 26th IEEE international conference on tools with artificial intelligence (ICTAI’14), IEEE Computer Society (pp. 170–177).

  • Sinz, C. (2005). Towards an optimal CNF encoding of Boolean cardinality constraints. In van Beek, P. (Ed.), Proceedings of the eleventh international conference on principles and practice of constraint programming (CP’05) (Vol. 3709, pp. 827–831). Springer, LNCS.

  • Soh, T., Banbara, M., Tamura, N., & Berre, D. L. (2017). Solving multiobjective discrete optimization problems with propositional minimal model generation. In J. C. Beck (Ed.), Proceedings of the 23rd international conference on principles and practice of constraint programming (CP’17) (Vol. 10416, pp. 596–614). Springer, LNCS.

  • Zivan, R., Grubshtein, A., & Meisels, A. (2011). Hybrid search for minimal perturbation in dynamic CSPs. Constraints, 16(3), 228–249.

    Article  Google Scholar 

Download references

Acknowledgements

Funding was provided by Japan Society for the Promotion of Science (Grant Nos. JSPS KAKENHI 15K00099, JSPS KAKENHI 16H02803) and Deutsche Forschungsgemeinschaft (Grant Nos. SCHA 550/9-2 and SCHA 550/11-1).

Author information

Authors and Affiliations

  1. Kobe University, 1-1 Rokko-dai, Nada-ku, Kobe, Hyogo, 657-8501, Japan

    Mutsunori Banbara, Tenda Okimoto, Takehide Soh & Naoyuki Tamura

  2. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

    Katsumi Inoue

  3. Universität Potsdam, August-Bebel-Strasse 89, 14482, Potsdam, Germany

    Benjamin Kaufmann, Torsten Schaub & Philipp Wanko

  4. Inria – Centre de Rennes Bretagne Atlantique, Rennes, France

    Torsten Schaub

  5. Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8550, Japan

    Katsumi Inoue

Authors
  1. Mutsunori Banbara
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Katsumi Inoue
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Benjamin Kaufmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tenda Okimoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Torsten Schaub
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Takehide Soh
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Naoyuki Tamura
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Philipp Wanko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mutsunori Banbara.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Banbara, M., Inoue, K., Kaufmann, B. et al. \({\varvec{teaspoon}}\): solving the curriculum-based course timetabling problems with answer set programming. Ann Oper Res 275, 3–37 (2019). https://doi.org/10.1007/s10479-018-2757-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-018-2757-7

Keywords

Search

Navigation