Please use this identifier to cite or link to this item:
http://repositorio.unicamp.br/jspui/handle/REPOSIP/329875
Type: | Artigo |
Title: | Lower bounds for large traveling umpire instances: new valid inequalities and a branch-and-cut algorithm |
Author: | Oliveira, Lucas de Souza, Cid C. de Yunes, Tallys |
Abstract: | Given a double round-robin tournament, the Traveling Umpire Problem (TUP) seeks to assign umpires to the games of the tournament while minimizing the total distance traveled by the umpires. The assignment must satisfy constraints that prevent umpires from seeing teams and venues too often, while making sure all games have umpires in every round, and all umpires visit all venues. We propose a new integer programming model for the TUP that generalizes the two best existing models, introduce new families of strong valid inequalities, and implement a branch-and-cut algorithm to solve instances from the TUP benchmark. When compared against published state-of-the-art methods, our algorithm significantly improves all best known lower bounds for large TUP instances (with 20 or more teams). (C) 2016 Elsevier Ltd. All rights reserved. Given a double round-robin tournament, the Traveling Umpire Problem (TUP) seeks to assign umpires to the games of the tournament while minimizing the total distance traveled by the umpires. The assignment must satisfy constraints that prevent umpires from |
Subject: | Sports Scheduling Traveling Umpire Problem Integer Programming Branch-and-cut Or In Sports Algoritmos branch-and-cut Programação inteira Esportes - Planejamento Complexidade computacional Otimização combinatória |
Country: | Reino Unido |
Editor: | Elsevier |
Citation: | Computers & Operations Research. Pergamon-elsevier Science Ltd , v. 72, p. 147 - 159, 2016. |
Rights: | fechado Fechado |
Identifier DOI: | 10.1016/j.cor.2016.02.014 |
Address: | https://www.sciencedirect.com/science/article/pii/S0305054816300387 |
Date Issue: | 2016 |
Appears in Collections: | IC - Artigos e Outros Documentos |
Files in This Item:
File | Size | Format | |
---|---|---|---|
000375502800013.pdf | 565.5 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.