Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/319986
Type: Artigo de Periódico
Title: Lower Bounds For Large Traveling Umpire Instances: New Valid Inequalities And A Branch-and-cut Algorithm
Author: de Oliveira
L; de Souza
CC; Yunes
T
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.
Subject: Sports Scheduling
Traveling Umpire Problem
Integer Programming
Branch-and-cut
Or In Sports
Editor: PERGAMON-ELSEVIER SCIENCE LTD
Rights: fechado
Identifier DOI: 10.1016/j.cor.2016.02.014
Address: http://www-sciencedirect-com.ez88.periodicos.capes.gov.br/science/article/pii/S0305054816300387
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000375502800013.pdf495.03 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.