The sport teams grouping problem

Tulio A.M. Toffolo (Corresponding author), Jan Christiaens, Frits C.R. Spieksma, Greet Vanden Berghe

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.
LanguageEnglish
Pages223-243
Number of pages21
JournalAnnals of Operations Research
Volume275
Issue number1
DOIs
StatePublished - Apr 2019

Keywords

  • Sport teams grouping problem
  • Branch-and-price
  • Column generation
  • Decomposition strategies
  • Integer programming
  • Meta-heuristic

Cite this

Toffolo, T. A. M., Christiaens, J., Spieksma, F. C. R., & Vanden Berghe, G. (2019). The sport teams grouping problem. Annals of Operations Research, 275(1), 223-243. DOI: 10.1007/s10479-017-2595-z
Toffolo, Tulio A.M. ; Christiaens, Jan ; Spieksma, Frits C.R. ; Vanden Berghe, Greet. / The sport teams grouping problem. In: Annals of Operations Research. 2019 ; Vol. 275, No. 1. pp. 223-243
@article{7c27f75ffb0f44c797ceb0fd4818247f,
title = "The sport teams grouping problem",
abstract = "The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7{\%} of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.",
keywords = "Sport teams grouping problem, Branch-and-price, Column generation, Decomposition strategies, Integer programming, Meta-heuristic",
author = "Toffolo, {Tulio A.M.} and Jan Christiaens and Spieksma, {Frits C.R.} and {Vanden Berghe}, Greet",
year = "2019",
month = "4",
doi = "10.1007/s10479-017-2595-z",
language = "English",
volume = "275",
pages = "223--243",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",
number = "1",

}

Toffolo, TAM, Christiaens, J, Spieksma, FCR & Vanden Berghe, G 2019, 'The sport teams grouping problem' Annals of Operations Research, vol. 275, no. 1, pp. 223-243. DOI: 10.1007/s10479-017-2595-z

The sport teams grouping problem. / Toffolo, Tulio A.M. (Corresponding author); Christiaens, Jan; Spieksma, Frits C.R.; Vanden Berghe, Greet.

In: Annals of Operations Research, Vol. 275, No. 1, 04.2019, p. 223-243.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The sport teams grouping problem

AU - Toffolo,Tulio A.M.

AU - Christiaens,Jan

AU - Spieksma,Frits C.R.

AU - Vanden Berghe,Greet

PY - 2019/4

Y1 - 2019/4

N2 - The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.

AB - The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.

KW - Sport teams grouping problem

KW - Branch-and-price

KW - Column generation

KW - Decomposition strategies

KW - Integer programming

KW - Meta-heuristic

U2 - 10.1007/s10479-017-2595-z

DO - 10.1007/s10479-017-2595-z

M3 - Article

VL - 275

SP - 223

EP - 243

JO - Annals of Operations Research

T2 - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -

Toffolo TAM, Christiaens J, Spieksma FCR, Vanden Berghe G. The sport teams grouping problem. Annals of Operations Research. 2019 Apr;275(1):223-243. Available from, DOI: 10.1007/s10479-017-2595-z