Home > Research > Publications & Outputs > A combined local search and integer programming...

Research

Associated organisational unit

Links

Text available via DOI:

Keywords

View graph of relations

A combined local search and integer programming approach to the traveling tournament problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A combined local search and integer programming approach to the traveling tournament problem. / Goerigk, Marc; Westphal, Stephan.
In: Annals of Operations Research, Vol. 239, No. 1, 04.2016, p. 343-354.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Goerigk, M & Westphal, S 2016, 'A combined local search and integer programming approach to the traveling tournament problem', Annals of Operations Research, vol. 239, no. 1, pp. 343-354. https://doi.org/10.1007/s10479-014-1586-6

APA

Goerigk, M., & Westphal, S. (2016). A combined local search and integer programming approach to the traveling tournament problem. Annals of Operations Research, 239(1), 343-354. https://doi.org/10.1007/s10479-014-1586-6

Vancouver

Goerigk M, Westphal S. A combined local search and integer programming approach to the traveling tournament problem. Annals of Operations Research. 2016 Apr;239(1):343-354. Epub 2014 Apr 6. doi: 10.1007/s10479-014-1586-6

Author

Goerigk, Marc ; Westphal, Stephan. / A combined local search and integer programming approach to the traveling tournament problem. In: Annals of Operations Research. 2016 ; Vol. 239, No. 1. pp. 343-354.

Bibtex

@article{79c2d88387214e308299751cae0c6cfb,
title = "A combined local search and integer programming approach to the traveling tournament problem",
abstract = "The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances. ",
keywords = "Integer programming, Sports scheduling, Tabu search, Traveling tournament problem",
author = "Marc Goerigk and Stephan Westphal",
year = "2016",
month = apr,
doi = "10.1007/s10479-014-1586-6",
language = "English",
volume = "239",
pages = "343--354",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",
number = "1",

}

RIS

TY - JOUR

T1 - A combined local search and integer programming approach to the traveling tournament problem

AU - Goerigk, Marc

AU - Westphal, Stephan

PY - 2016/4

Y1 - 2016/4

N2 - The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances. 

AB - The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances. 

KW - Integer programming

KW - Sports scheduling

KW - Tabu search

KW - Traveling tournament problem

U2 - 10.1007/s10479-014-1586-6

DO - 10.1007/s10479-014-1586-6

M3 - Journal article

AN - SCOPUS:84897346383

VL - 239

SP - 343

EP - 354

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -