{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T06:21:27Z","timestamp":1778739687237,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,18]],"date-time":"2022-06-18T00:00:00Z","timestamp":1655510400000},"content-version":"vor","delay-in-days":17,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We report on the development of Reprobate, a tool for solving sports timetabling problems in a subset of the RobinX format. Our tool is based around a monolithic translation of a sports timetabling instance into a pseudo-Boolean (PB) optimisation problem; this instance can be solved using existing pseudo-Boolean solvers. Once the tool has found a feasible solution, it can improve it using a second encoding that alters only the home\/away pattern of games. We entered our tool into the International Timetabling Competition 2021. While it was effective on many instances, it struggled to cope with schedules involving large break constraints. However, among instances for which it could initially find a feasible solution, the combination of use of a portfolio of solvers, a range of variations on the encoding and the aforementioned local improvement process yielded an average reduction in solution cost of 23%.<\/jats:p>","DOI":"10.1007\/s10951-022-00737-7","type":"journal-article","created":{"date-parts":[[2022,6,18]],"date-time":"2022-06-18T08:02:52Z","timestamp":1655539372000},"page":"287-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Pseudo-Boolean optimisation for RobinX sports timetabling"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2323-1771","authenticated-orcid":false,"given":"Martin Mariusz","family":"Lester","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,18]]},"reference":[{"issue":"1","key":"737_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.3233\/SAT190119","volume":"11","author":"F Bacchus","year":"2019","unstructured":"Bacchus, F., J\u00e4rvisalo, M., & Martins, R. (2019). MaxSAT evaluation 2018: New developments and detailed results. Journal on Satisfiability, Boolean Modeling and Computation, 11(1), 99\u2013131. https:\/\/doi.org\/10.3233\/SAT190119.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"issue":"2","key":"737_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/05695557708975138","volume":"9","author":"BC Ball","year":"1977","unstructured":"Ball, B. C., & Webster, D. B. (1977). Optimal scheduling for even-numbered team athletic conferences. AIIE Transactions, 9(2), 161\u2013169. https:\/\/doi.org\/10.1080\/05695557708975138.","journal-title":"AIIE Transactions"},{"issue":"2\u20133","key":"737_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3233\/sat190075","volume":"7","author":"DL Berre","year":"2010","unstructured":"Berre, D. L., & Parrain, A. (2010). The Sat4j library, release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 7(2\u20133), 59\u201364. https:\/\/doi.org\/10.3233\/sat190075.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"737_CR4","unstructured":"Berthold, T., Heinz, S., & Pfetsch, M. (2008). Solving pseudo-Boolean problems with SCIP. Technical Report 08-12, ZIB, Takustr. 7, 14195 Berlin. https:\/\/nbn-resolving.org\/urn:nbn:de:0297-zib-10671."},{"key":"737_CR5","doi-asserted-by":"publisher","unstructured":"Devriendt, J., Bogaerts, B., Bruynooghe, M., & Denecker, M. (2016). Improved static symmetry breaking for SAT. In N. Creignou, & D. L. Berre (Eds.), Theory and applications of satisfiability testing\u2014SAT 2016\u201319th international conference, Bordeaux, France, July 5\u20138, 2016, proceedings. Lecture notes in computer science (Vol. 9710, pp. 104\u2013122). Springer. https:\/\/doi.org\/10.1007\/978-3-319-40970-2_8.","DOI":"10.1007\/978-3-319-40970-2_8"},{"issue":"1","key":"737_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s10601-020-09318-x","volume":"26","author":"J Devriendt","year":"2021","unstructured":"Devriendt, J., Gleixner, A. M., & Nordstr\u00f6m, J. (2021). Learn to relax: Integrating 0\u20131 integer linear programming with pseudo-Boolean conflict-driven search. Constraints, 26(1), 26\u201355. https:\/\/doi.org\/10.1007\/s10601-020-09318-x.","journal-title":"Constraints"},{"issue":"1\u20134","key":"737_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/sat190014","volume":"2","author":"N E\u00e9n","year":"2006","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2006). Translating pseudo-Boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation, 2(1\u20134), 1\u201326. https:\/\/doi.org\/10.3233\/sat190014.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"737_CR8","doi-asserted-by":"publisher","unstructured":"Elffers, J., & Nordstr\u00f6m, J. (2018). Divide and conquer: Towards faster pseudo-Boolean solving. In J. Lang (Ed.), Proceedings of the twenty-seventh international joint conference on artificial intelligence, IJCAI 2018, July 13\u201319, 2018, Stockholm, Sweden (pp. 1291\u20131299). ijcai.org. https:\/\/doi.org\/10.24963\/ijcai.2018\/180.","DOI":"10.24963\/ijcai.2018\/180"},{"key":"737_CR9","doi-asserted-by":"publisher","unstructured":"Elffers, J., Gir\u00e1ldez-Cru, J., Nordstr\u00f6m, J., & Vinyals, M. (2018). Using combinatorial benchmarks to probe the reasoning power of pseudo-Boolean solvers. In O. Beyersdorff, & C. M. Wintersteiger (Eds.), Theory and applications of satisfiability testing\u2014SAT 2018\u201421st international conference, SAT 2018, held as part of the federated logic conference, FloC 2018, Oxford, UK, July 9\u201312, 2018, proceedings. Lecture notes in computer science (Vol. 10929, pp. 75\u201393). Springer. https:\/\/doi.org\/10.1007\/978-3-319-94144-8_5.","DOI":"10.1007\/978-3-319-94144-8_5"},{"issue":"52\u201389","key":"737_CR10","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.artint.2012.04.001","volume":"187","author":"M Gebser","year":"2012","unstructured":"Gebser, M., Kaufmann, B., & Schaub, T. (2012). Conflict-driven answer set solving: From theory to practice. Artificial Intelligence, 187(52\u201389), 10. https:\/\/doi.org\/10.1016\/j.artint.2012.04.001.","journal-title":"Artificial Intelligence"},{"key":"737_CR11","unstructured":"Gent, I. P., & Lynce, I. (2005). A SAT encoding for the social golfer problem. In IJCAI\u201905 Workshop on modelling and solving problems with constraints. https:\/\/www.inesc-id.pt\/ficheiros\/publicacoes\/2516.pdf."},{"key":"737_CR12","unstructured":"Harvey, W. (1999). CSPLib Problem 010: Social Golfers problem. http:\/\/www.csplib.org\/Problems\/prob010."},{"key":"737_CR13","doi-asserted-by":"publisher","unstructured":"Henz, M. (1999). Constraint-based round robin tournament planning. In D.D. Schreye (Ed.), Logic programming: The 1999 international conference, Las Cruces, New Mexico, USA, November 29\u2013December 4, 1999 (pp. 545\u2013557). MIT Press. https:\/\/doi.org\/10.5555\/341176.341272.","DOI":"10.5555\/341176.341272"},{"key":"737_CR14","doi-asserted-by":"crossref","unstructured":"Henz, M. (2001). Scheduling a major college basketball conference-revisited. Operations Research, 49(1), 163\u2013168. http:\/\/www.jstor.org\/stable\/222963.","DOI":"10.1287\/opre.49.1.163.11193"},{"issue":"1","key":"737_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10951-010-0194-9","volume":"15","author":"A Horbach","year":"2012","unstructured":"Horbach, A., Bartsch, T., & Briskorn, D. (2012). Using a SAT-solver to schedule sports leagues. Journal of Scheduling, 15(1), 117\u2013125. https:\/\/doi.org\/10.1007\/s10951-010-0194-9.","journal-title":"Journal of Scheduling"},{"key":"737_CR16","doi-asserted-by":"publisher","unstructured":"Lardeux, F., & Monfroy, E. (2015). Expressively modeling the social golfer problem in SAT. In S. Koziel, L. Leifsson, M. Lees, V. V. Krzhizhanovskaya, J. J. Dongarra, & P. M. A. Sloot (Eds.), Proceedings of the international conference on computational science, ICCS 2015, computational science at the gates of nature, Reykjav\u00edk, Iceland, 1\u20133 June, 2015, 2014. Procedia computer science (Vol. 51, pp. 336\u2013345). Elsevier. https:\/\/doi.org\/10.1016\/j.procs.2015.05.252.","DOI":"10.1016\/j.procs.2015.05.252"},{"key":"737_CR17","doi-asserted-by":"publisher","unstructured":"Lester, M. (2021). Reprobate. https:\/\/doi.org\/10.5281\/zenodo.5084254","DOI":"10.5281\/zenodo.5084254"},{"key":"737_CR18","doi-asserted-by":"publisher","unstructured":"Lester, M. M. (2021). Scheduling reach mahjong tournaments using pseudoboolean constraints. In C. Li, & F. Many\u00e0 (Eds.), Theory and applications of satisfiability testing\u2014SAT 2021\u201424th international conference, Barcelona, Spain, July 5\u20139, 2021, proceedings. Lecture notes in computer science (Vol. 12831, pp. 349\u2013358). Springer. https:\/\/doi.org\/10.1007\/978-3-030-80223-3_24.","DOI":"10.1007\/978-3-030-80223-3_24"},{"issue":"1\u20134","key":"737_CR19","doi-asserted-by":"publisher","first-page":"103","DOI":"10.3233\/sat190018","volume":"2","author":"VM Manquinho","year":"2006","unstructured":"Manquinho, V. M., & Roussel, O. (2006). The first evaluation of pseudo-Boolean solvers (PB\u201905). Journal on Satisfiability, Boolean Modeling and Computation, 2(1\u20134), 103\u2013143. https:\/\/doi.org\/10.3233\/sat190018.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"737_CR20","doi-asserted-by":"publisher","unstructured":"Philipp, T., & Steinke, P. (2015). PBLib\u2014A library for encoding pseudo-Boolean constraints into CNF. In M. Heule, & S. A. Weaver (Eds.), Theory and applications of satisfiability testing\u2014SAT 2015\u201418th international conference, Austin, TX, USA, September 24\u201327, 2015, proceedings. Lecture notes in computer science (Vol. 9340, pp. 9\u201316). Springer. https:\/\/doi.org\/10.1007\/978-3-319-24318-4_2","DOI":"10.1007\/978-3-319-24318-4_2"},{"issue":"3","key":"737_CR21","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.ejor.2007.05.046","volume":"188","author":"RV Rasmussen","year":"2008","unstructured":"Rasmussen, R. V., & Trick, M. A. (2008). Round robin scheduling\u2013a survey. European Journal of Operational Research, 188(3), 617\u2013636. https:\/\/doi.org\/10.1016\/j.ejor.2007.05.046.","journal-title":"European Journal of Operational Research"},{"key":"737_CR22","doi-asserted-by":"publisher","unstructured":"Trick, M. A. (2000). A schedule-then-break approach to sports timetabling. In E. K. Burke, & W. Erben (Eds.), Practice and theory of automated timetabling III, third international conference, PATAT 2000, Konstanz, Germany, August 16\u201318, 2000, selected papers. Lecture notes in computer science (Vol. 2079, pp. 242\u2013253). Springer. https:\/\/doi.org\/10.1007\/3-540-44629-X_15.","DOI":"10.1007\/3-540-44629-X_15"},{"key":"737_CR23","doi-asserted-by":"publisher","unstructured":"Triska, M., & Musliu, N. (2012a). An improved SAT formulation for the social golfer problem. Annals of Operations Research, 194(1), 427\u2013438. https:\/\/doi.org\/10.1007\/s10479-010-0702-5.","DOI":"10.1007\/s10479-010-0702-5"},{"key":"737_CR24","doi-asserted-by":"publisher","unstructured":"Triska, M., & Musliu, N. (2012b). An effective greedy heuristic for the social golfer problem. Annals of Operations Research, 194(1), 413\u2013425. https:\/\/doi.org\/10.1007\/s10479-011-0866-7.","DOI":"10.1007\/s10479-011-0866-7"},{"key":"737_CR25","unstructured":"Van Bulck, D., Goossens, D. R., Beli\u00ebn, J., & Davari, M. (2020a). ITC2021\u2014Sports Timetabling Problem Description and File Format. https:\/\/www.sportscheduling.ugent.be\/ITC2021\/images\/OrganizationITC2021_V7.pdf."},{"key":"737_CR26","unstructured":"Van Bulck, D., Goossens, D. R., Beli\u00ebn, J., & Davari, M. (2021). The fifth International Timetabling Competition (ITC 2021): Sports timetabling. In Proceedings of MathSport international 2021 conference (pp. 117\u2013122). http:\/\/www.mathsportinternational.com\/MathSport2021Proceedings.pdf."},{"key":"737_CR27","doi-asserted-by":"publisher","unstructured":"Van Bulck, D., Goossens, D. R., Sch\u00f6nberger, J., & Guajardo, M. (2020b). RobinX: A three-field classification and unified data format for round-robin sports timetabling. European Journal of Operational Research, 280(2), 568\u2013580. https:\/\/doi.org\/10.1016\/j.ejor.2019.07.023.","DOI":"10.1016\/j.ejor.2019.07.023"},{"key":"737_CR28","unstructured":"Walser, J. P. (1998) AMPL model of \u2018Maximum socializing on the golf course\u2019. https:\/\/www.csplib.org\/Problems\/prob010\/models\/AMPLmodel.txt.html."},{"key":"737_CR29","unstructured":"Zhang, H. (2002). Generating college conference basketball schedules by a SAT solver. In Proceedings of the fifth international symposium on the theory and applications of satisfiability testing, Cincinnati (pp. 281\u2013291). http:\/\/gauss.ececs.uc.edu\/Conferences\/SAT2002\/Abstracts\/zhang.ps."},{"key":"737_CR30","unstructured":"Zhang, H., Li, D., & Shen, H. (2004). A SAT based scheduler for tournament schedules. In SAT 2004\u2014the seventh international conference on theory and applications of satisfiability testing, 10\u201313 May 2004, Vancouver, BC, Canada, online proceedings. http:\/\/www.satisfiability.org\/SAT04\/programme\/74.pdf."},{"key":"737_CR31","doi-asserted-by":"publisher","unstructured":"Zhou, N.-F., Kjellerstrand, H., & Fruhman, J. (2015). Encodings for the traveling salesman problem (pp. 129\u2013139). Springer. https:\/\/doi.org\/10.1007\/978-3-319-25883-6_7.","DOI":"10.1007\/978-3-319-25883-6_7"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00737-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00737-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00737-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T10:35:58Z","timestamp":1657190158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00737-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["737"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00737-7","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6]]},"assertion":[{"value":"3 May 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}