The Traveling Tournament Problem: Rows-First versus Columns-First

Kristian Verduin; Ruben Horn; Okke van Eck; Reitze Jansen; Thomas Weise; Daan van den Berg

doi:10.5220/0012557700003690

The Traveling Tournament Problem: Rows-First versus Columns-First

Kristian Verduin, Ruben Horn, Okke van Eck, Reitze Jansen, Thomas Weise, Daan van den Berg

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

At the time of writing, there is no known deterministic time algorithm to uniformly sample initial valid solutions for the traveling tournament problem, severely impeding any evolutionary approach that would need a random initial population. Repeatedly random sampling initial solutions until we find a valid one is apparently the best we can do, but even this rather crude method still requires exponential time. It does make a difference however, if one chooses to generate initial schedules column-by-column or row-by-row.

Original language	English
Title of host publication	Proceedings of the 26th International Conference on Enterprise Information Systems
Subtitle of host publication	Volume 1: ICEIS
Editors	Joaquim Filipe, Michal Smialek, Alexander Brodsky, Slimane Hammoudi
Publisher	Science and Technology Publications, Lda
Pages	447-455
Number of pages	9
Volume	1
ISBN (Electronic)	9789897586927
DOIs	https://doi.org/10.5220/0012557700003690
Publication status	Published - 2024
Event	26th International Conference on Enterprise Information Systems, ICEIS 2024 - Angers, France Duration: 28 Apr 2024 → 30 Apr 2024

Publication series

Name	International Conference on Enterprise Information Systems, ICEIS - Proceedings
ISSN (Electronic)	2184-4992

Conference

Conference	26th International Conference on Enterprise Information Systems, ICEIS 2024
Country/Territory	France
City	Angers
Period	28/04/24 → 30/04/24

Bibliographical note

Publisher Copyright:
Copyright © 2024 by SCITEPRESS – Science and Technology Publications, Lda.

Keywords

Constraint Hierarchy
Constraints
Evolutionary Computing
Genetic Algorithms
Traveling Tournament Problem

Access to Document

10.5220/0012557700003690Licence: CC BY-NC-ND

Persistent URL (handle)

Persistent link

Cite this

Verduin, K., Horn, R., van Eck, O., Jansen, R., Weise, T., & van den Berg, D. (2024). The Traveling Tournament Problem: Rows-First versus Columns-First. In J. Filipe, M. Smialek, A. Brodsky, & S. Hammoudi (Eds.), Proceedings of the 26th International Conference on Enterprise Information Systems: Volume 1: ICEIS (Vol. 1, pp. 447-455). (International Conference on Enterprise Information Systems, ICEIS - Proceedings). Science and Technology Publications, Lda. https://doi.org/10.5220/0012557700003690

Verduin, Kristian ; Horn, Ruben ; van Eck, Okke et al. / The Traveling Tournament Problem : Rows-First versus Columns-First. Proceedings of the 26th International Conference on Enterprise Information Systems: Volume 1: ICEIS. editor / Joaquim Filipe ; Michal Smialek ; Alexander Brodsky ; Slimane Hammoudi. Vol. 1 Science and Technology Publications, Lda, 2024. pp. 447-455 (International Conference on Enterprise Information Systems, ICEIS - Proceedings).

@inproceedings{4b9306b07f3e4b6da3f80568ba790372,

title = "The Traveling Tournament Problem: Rows-First versus Columns-First",

abstract = "At the time of writing, there is no known deterministic time algorithm to uniformly sample initial valid solutions for the traveling tournament problem, severely impeding any evolutionary approach that would need a random initial population. Repeatedly random sampling initial solutions until we find a valid one is apparently the best we can do, but even this rather crude method still requires exponential time. It does make a difference however, if one chooses to generate initial schedules column-by-column or row-by-row.",

keywords = "Constraint Hierarchy, Constraints, Evolutionary Computing, Genetic Algorithms, Traveling Tournament Problem",

author = "Kristian Verduin and Ruben Horn and {van Eck}, Okke and Reitze Jansen and Thomas Weise and {van den Berg}, Daan",

note = "Publisher Copyright: Copyright {\textcopyright} 2024 by SCITEPRESS – Science and Technology Publications, Lda.; 26th International Conference on Enterprise Information Systems, ICEIS 2024 ; Conference date: 28-04-2024 Through 30-04-2024",

year = "2024",

doi = "10.5220/0012557700003690",

language = "English",

volume = "1",

series = "International Conference on Enterprise Information Systems, ICEIS - Proceedings",

publisher = "Science and Technology Publications, Lda",

pages = "447--455",

editor = "Joaquim Filipe and Michal Smialek and Alexander Brodsky and Slimane Hammoudi",

booktitle = "Proceedings of the 26th International Conference on Enterprise Information Systems",

}

Verduin, K, Horn, R, van Eck, O, Jansen, R, Weise, T & van den Berg, D 2024, The Traveling Tournament Problem: Rows-First versus Columns-First. in J Filipe, M Smialek, A Brodsky & S Hammoudi (eds), Proceedings of the 26th International Conference on Enterprise Information Systems: Volume 1: ICEIS. vol. 1, International Conference on Enterprise Information Systems, ICEIS - Proceedings, Science and Technology Publications, Lda, pp. 447-455, 26th International Conference on Enterprise Information Systems, ICEIS 2024, Angers, France, 28/04/24. https://doi.org/10.5220/0012557700003690

The Traveling Tournament Problem: Rows-First versus Columns-First. / Verduin, Kristian; Horn, Ruben; van Eck, Okke et al.
Proceedings of the 26th International Conference on Enterprise Information Systems: Volume 1: ICEIS. ed. / Joaquim Filipe; Michal Smialek; Alexander Brodsky; Slimane Hammoudi. Vol. 1 Science and Technology Publications, Lda, 2024. p. 447-455 (International Conference on Enterprise Information Systems, ICEIS - Proceedings).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Traveling Tournament Problem

T2 - 26th International Conference on Enterprise Information Systems, ICEIS 2024

AU - Verduin, Kristian

AU - Horn, Ruben

AU - van Eck, Okke

AU - Jansen, Reitze

AU - Weise, Thomas

AU - van den Berg, Daan

PY - 2024

Y1 - 2024

N2 - At the time of writing, there is no known deterministic time algorithm to uniformly sample initial valid solutions for the traveling tournament problem, severely impeding any evolutionary approach that would need a random initial population. Repeatedly random sampling initial solutions until we find a valid one is apparently the best we can do, but even this rather crude method still requires exponential time. It does make a difference however, if one chooses to generate initial schedules column-by-column or row-by-row.

AB - At the time of writing, there is no known deterministic time algorithm to uniformly sample initial valid solutions for the traveling tournament problem, severely impeding any evolutionary approach that would need a random initial population. Repeatedly random sampling initial solutions until we find a valid one is apparently the best we can do, but even this rather crude method still requires exponential time. It does make a difference however, if one chooses to generate initial schedules column-by-column or row-by-row.

KW - Constraint Hierarchy

KW - Constraints

KW - Evolutionary Computing

KW - Genetic Algorithms

KW - Traveling Tournament Problem

UR - http://www.scopus.com/inward/record.url?scp=85193915734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85193915734&partnerID=8YFLogxK

U2 - 10.5220/0012557700003690

DO - 10.5220/0012557700003690

M3 - Conference contribution

AN - SCOPUS:85193915734

VL - 1

T3 - International Conference on Enterprise Information Systems, ICEIS - Proceedings

SP - 447

EP - 455

BT - Proceedings of the 26th International Conference on Enterprise Information Systems

A2 - Filipe, Joaquim

A2 - Smialek, Michal

A2 - Brodsky, Alexander

A2 - Hammoudi, Slimane

PB - Science and Technology Publications, Lda

Y2 - 28 April 2024 through 30 April 2024

ER -

Verduin K, Horn R, van Eck O, Jansen R, Weise T, van den Berg D. The Traveling Tournament Problem: Rows-First versus Columns-First. In Filipe J, Smialek M, Brodsky A, Hammoudi S, editors, Proceedings of the 26th International Conference on Enterprise Information Systems: Volume 1: ICEIS. Vol. 1. Science and Technology Publications, Lda. 2024. p. 447-455. (International Conference on Enterprise Information Systems, ICEIS - Proceedings). doi: 10.5220/0012557700003690

The Traveling Tournament Problem: Rows-First versus Columns-First

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this