Skip to main content
Top

2017 | OriginalPaper | Chapter

Solving the Travelling Umpire Problem with Answer Set Programming

Author : Joost Vennekens

Published in: BNAIC 2016: Artificial Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we develop an Answer Set Programming (ASP) solution to the Travelling Umpire Problem (TUP). We investigate a number of different ways to improve the computational performance of this solution and compare it to the current state-of-the-art. Our results demonstrate that the ASP solution is superior to other declarative solutions, such as Constraint Programming, but that it cannot match the most recent special-purpose algorithms from the literature. However, when compared to the earlier generation of special-purpose algorithms, it does quite well.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Pührer, J., Redl, C., Ricca, F., Schneider, P., Schwengerer, M., Spendier, L.K., Wallner, J.P., Xiao, G.: The fourth answer set programming competition: preliminary report. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 42–53. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40564-8_5 CrossRef Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Pührer, J., Redl, C., Ricca, F., Schneider, P., Schwengerer, M., Spendier, L.K., Wallner, J.P., Xiao, G.: The fourth answer set programming competition: preliminary report. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 42–53. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40564-8_​5 CrossRef
2.
go back to reference Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: Design and results of the fifth answer set programming competition. Artif. Intell. 231, 151–181 (2016)MathSciNetCrossRefMATH Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: Design and results of the fifth answer set programming competition. Artif. Intell. 231, 151–181 (2016)MathSciNetCrossRefMATH
3.
go back to reference Calimeri, F., et al.: The third answer set programming competition: preliminary report of the system competition track. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 388–403. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20895-9_46 CrossRef Calimeri, F., et al.: The third answer set programming competition: preliminary report of the system competition track. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS, vol. 6645, pp. 388–403. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20895-9_​46 CrossRef
4.
go back to reference de Oliveira, L., de Souza, C., Yunes, T.: Improved bounds for the traveling umpire problem: a stronger formulation and a relax-and-fix heuristic. EJOR 2, 592–600 (2014)MathSciNetCrossRefMATH de Oliveira, L., de Souza, C., Yunes, T.: Improved bounds for the traveling umpire problem: a stronger formulation and a relax-and-fix heuristic. EJOR 2, 592–600 (2014)MathSciNetCrossRefMATH
5.
go back to reference de Oliveira, L., de Souza, C., Yunes, T.: On the complexity of the traveling umpire problem. Theor. Comput. Sci. 562, 101–111 (2015)MathSciNetCrossRefMATH de Oliveira, L., de Souza, C., Yunes, T.: On the complexity of the traveling umpire problem. Theor. Comput. Sci. 562, 101–111 (2015)MathSciNetCrossRefMATH
6.
go back to reference Denecker, M., Vennekens, J., Bond, S., Gebser, M., Truszczyński, M.: The second answer set programming competition. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS, vol. 5753, pp. 637–654. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04238-6_75 CrossRef Denecker, M., Vennekens, J., Bond, S., Gebser, M., Truszczyński, M.: The second answer set programming competition. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS, vol. 5753, pp. 637–654. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04238-6_​75 CrossRef
7.
go back to reference Gebser, M., Harrison, A., Kaminski, R., Lifschitz, V., Schaub, T.: Abstract gringo. In: TPLP (2015) Gebser, M., Harrison, A., Kaminski, R., Lifschitz, V., Schaub, T.: Abstract gringo. In: TPLP (2015)
8.
go back to reference Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: the potsdam answer set solving collection. AI Communications 24(2), 107–124 (2011)MathSciNetMATH Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: the potsdam answer set solving collection. AI Communications 24(2), 107–124 (2011)MathSciNetMATH
9.
go back to reference Baral, C., Brewka, G., Schlipf, J. (eds.): LPNMR 2007. LNCS (LNAI), vol. 4483. Springer, Heidelberg (2007)MATH Baral, C., Brewka, G., Schlipf, J. (eds.): LPNMR 2007. LNCS (LNAI), vol. 4483. Springer, Heidelberg (2007)MATH
10.
go back to reference Gebser, M., Maratea, M., Ricca, F.: The design of the sixth answer set programming competition. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS, vol. 9345, pp. 531–544. Springer, Cham (2015). doi:10.1007/978-3-319-23264-5_44 CrossRef Gebser, M., Maratea, M., Ricca, F.: The design of the sixth answer set programming competition. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS, vol. 9345, pp. 531–544. Springer, Cham (2015). doi:10.​1007/​978-3-319-23264-5_​44 CrossRef
11.
go back to reference Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R., Bowen, K. (eds.) ICLP, pp. 1070–1080. MIT Press, Cambridge (1988) Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R., Bowen, K. (eds.) ICLP, pp. 1070–1080. MIT Press, Cambridge (1988)
12.
go back to reference Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25566-3_40 CrossRef Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25566-3_​40 CrossRef
13.
go back to reference Toffolo, T., Van Malderen, S., Wauters, T.V., Berghe, G.: Branch-and-Price and Improved Bounds to the Traveling Umpire Problem. PATAT, York (2014)MATH Toffolo, T., Van Malderen, S., Wauters, T.V., Berghe, G.: Branch-and-Price and Improved Bounds to the Traveling Umpire Problem. PATAT, York (2014)MATH
14.
go back to reference Toffolo, T., Wauters, T., Van Malderen, S., Vanden Berghe, G.: Branch-and-bound with decomposition-based lower bounds for the traveling umpire problem. EJOR 3, 932–943 (2015)MATH Toffolo, T., Wauters, T., Van Malderen, S., Vanden Berghe, G.: Branch-and-bound with decomposition-based lower bounds for the traveling umpire problem. EJOR 3, 932–943 (2015)MATH
15.
go back to reference Trick, M.A., Yildiz, H.: Bender‘s cuts guided large neighborhood search for the traveling umpire problem. In: Van Hentenryck, P., Wolsey, L. (eds.) CPAIOR 2007. LNCS, vol. 4510, pp. 332–345. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72397-4_24 CrossRef Trick, M.A., Yildiz, H.: Bender‘s cuts guided large neighborhood search for the traveling umpire problem. In: Van Hentenryck, P., Wolsey, L. (eds.) CPAIOR 2007. LNCS, vol. 4510, pp. 332–345. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72397-4_​24 CrossRef
16.
go back to reference Trick, M., Yildiz, H.: Benders’ cuts guided large neighborhood search for the traveling umpire problem. Naval Res. Logistics (NRL) 8, 771–781 (2011)MathSciNetCrossRefMATH Trick, M., Yildiz, H.: Benders’ cuts guided large neighborhood search for the traveling umpire problem. Naval Res. Logistics (NRL) 8, 771–781 (2011)MathSciNetCrossRefMATH
17.
18.
go back to reference Trick, M., Yildiz, H., Yunes, T.: Scheduling major league baseball umpires and the traveling umpire problem. Interfaces 3, 232–244 (2012)CrossRef Trick, M., Yildiz, H., Yunes, T.: Scheduling major league baseball umpires and the traveling umpire problem. Interfaces 3, 232–244 (2012)CrossRef
20.
go back to reference Wauters, T., Van Malderen, S., Vanden Berghe, G.: Decomposition and local search based methods for the traveling umpire problem. EJOR 3, 886–898 (2014)MathSciNetCrossRefMATH Wauters, T., Van Malderen, S., Vanden Berghe, G.: Decomposition and local search based methods for the traveling umpire problem. EJOR 3, 886–898 (2014)MathSciNetCrossRefMATH
Metadata
Title
Solving the Travelling Umpire Problem with Answer Set Programming
Author
Joost Vennekens
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-67468-1_8

Premium Partner