IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v197y2009i1p68-76.html
   My bibliography  Save this article

A branching scheme for finding cost-minimal round robin tournaments

Author

Listed:
  • Briskorn, Dirk
  • Drexl, Andreas

Abstract

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home-away-pattern sets having the minimum number of breaks. A branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.

Suggested Citation

  • Briskorn, Dirk & Drexl, Andreas, 2009. "A branching scheme for finding cost-minimal round robin tournaments," European Journal of Operational Research, Elsevier, vol. 197(1), pages 68-76, August.
    • Handle: RePEc:eee:ejores:v:197:y:2009:i:1:p:68-76
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00472-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Rasmussen, Rasmus V. & Trick, Michael A., 2007. "A Benders approach for the constrained minimum break problem," European Journal of Operational Research, Elsevier, vol. 177(1), pages 198-213, February.
    2. Drexl, Andreas & Knust, Sigrid, 2007. "Sports league scheduling: Graph- and resource-based models," Omega, Elsevier, vol. 35(5), pages 465-471, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Horbach, Andrei & Bartsch, Thomas & Briskorn, Dirk, 2009. "Optimally scheduling real world sports leagues by reduction to SAT," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 646, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    2. Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre (Ed.), 2010. "Jahresbericht 2009," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 650, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Krumer, Alex & Megidish, Reut & Sela, Aner, 2023. "Strategic manipulations in round-robin tournaments," Mathematical Social Sciences, Elsevier, vol. 122(C), pages 50-57.
    4. Flavia Bonomo & Andrés Cardemil & Guillermo Durán & Javier Marenco & Daniela Sabán, 2012. "An Application of the Traveling Tournament Problem: The Argentine Volleyball League," Interfaces, INFORMS, vol. 42(3), pages 245-259, June.
    5. David Van Bulck & Dries Goossens & Jo¨rn Scho¨nberger & Mario Guajardo, 2020. "An Instance Data Repository for the Round-robin Sports Timetabling Problem," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 45(2), pages 184-200, May.
    6. Briskorn, Dirk, 2009. "A branching scheme for minimum cost tournaments with regard to real world constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 643, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Chen Cohen & Ishay Rabi & Aner Sela, 2023. "Optimal seedings in interdependent contests," Annals of Operations Research, Springer, vol. 328(2), pages 1263-1285, September.
    8. Irnich, Stefan, 2010. "A new branch-and-price algorithm for the traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 218-228, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. D Briskorn & A Drexl, 2009. "A branch-and-price algorithm for scheduling sport leagues," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 84-93, January.
    2. D Briskorn, 2011. "A branching scheme for minimum cost tournaments with regard to real-world constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2133-2145, December.
    3. Briskorn, Dirk & Drexl, Andreas, 2007. "A branching scheme based on First-Break-Then-Schedule decomposition," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 623, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Rasmussen, Rasmus V. & Trick, Michael A., 2008. "Round robin scheduling - a survey," European Journal of Operational Research, Elsevier, vol. 188(3), pages 617-636, August.
    5. Briskorn, Dirk & Horbach, Andrei, 2009. "A Lagrangian approach for minimum cost tournaments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 647, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Nicolau, Juan L., 2012. "The effect of winning the 2010 FIFA World Cup on the tourism market value: The Spanish case," Omega, Elsevier, vol. 40(5), pages 503-510.
    7. Riise, Atle & Mannino, Carlo & Lamorgese, Leonardo, 2016. "Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling," European Journal of Operational Research, Elsevier, vol. 255(3), pages 719-728.
    8. Hoshino, Richard & Kawarabayashi, Ken-ichi, 2011. "A multi-round generalization of the traveling tournament problem and its application to Japanese baseball," European Journal of Operational Research, Elsevier, vol. 215(2), pages 481-497, December.
    9. Roel Lambers & Dries Goossens & Frits C. R. Spieksma, 2023. "The flexibility of home away pattern sets," Journal of Scheduling, Springer, vol. 26(5), pages 413-423, October.
    10. Rasmussen, Rasmus V., 2008. "Scheduling a triple round robin tournament for the best Danish soccer league," European Journal of Operational Research, Elsevier, vol. 185(2), pages 795-810, March.
    11. M B Wright, 2009. "50 years of OR in sport," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 161-168, May.
    12. G Kendall, 2008. "Scheduling English football fixtures over holiday periods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 743-755, June.
    13. David Van Bulck & Dries Goossens, 2022. "Optimizing rest times and differences in games played: an iterative two-phase approach," Journal of Scheduling, Springer, vol. 25(3), pages 261-271, June.
    14. Yun-Chia Liang & Yen-Yu Lin & Angela Hsiang-Ling Chen & Wei-Sheng Chen, 2021. "Variable Neighborhood Search for Major League Baseball Scheduling Problem," Sustainability, MDPI, vol. 13(7), pages 1-18, April.
    15. Alex Krumer & Reut Megidish & Aner Sela, 2020. "The optimal design of round-robin tournaments with three players," Journal of Scheduling, Springer, vol. 23(3), pages 379-396, June.
    16. Turabieh, Hamza & Abdullah, Salwani, 2011. "An integrated hybrid approach to the examination timetabling problem," Omega, Elsevier, vol. 39(6), pages 598-607, December.
    17. Rasmus Rasmussen & Michael Trick, 2009. "The timetable constrained distance minimization problem," Annals of Operations Research, Springer, vol. 171(1), pages 45-59, October.
    18. Katarína Cechlárová & Ágnes Cseh & Zsuzsanna Jankó & Marián Kireš & Lukáš Miňo, 2023. "A quest for a fair schedule: The International Young Physicists’ Tournament," Journal of Scheduling, Springer, vol. 26(1), pages 3-18, February.
    19. Van Bulck, David & Goossens, Dries, 2023. "A traditional Benders’ approach to sports timetabling," European Journal of Operational Research, Elsevier, vol. 307(2), pages 813-826.
    20. Schauz, Uwe, 2016. "The tournament scheduling problem with absences," European Journal of Operational Research, Elsevier, vol. 254(3), pages 746-754.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:197:y:2009:i:1:p:68-76. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.