Lower Bounds For Large Traveling Umpire Instances: New Valid Inequalities And A Branch-and-cut Algorithm

dc.creatorde Oliveira
dc.creatorLucas; de Souza
dc.creatorCid C.; Yunes
dc.creatorTallys
dc.date2016
dc.dateagos
dc.date2017-11-13T13:56:31Z
dc.date2017-11-13T13:56:31Z
dc.date.accessioned2018-03-29T06:09:51Z
dc.date.available2018-03-29T06:09:51Z
dc.identifierComputers & Operations Research. Pergamon-elsevier Science Ltd , v. 72, p. 147 - 159, 2016.
dc.identifier0305-0548
dc.identifier1873-765X
dc.identifierWOS:000375502800013
dc.identifier10.1016/j.cor.2016.02.014
dc.identifierhttp://www-sciencedirect-com.ez88.periodicos.capes.gov.br/science/article/pii/S0305054816300387?via%3Dihub
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/329875
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1366900
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionGiven 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.
dc.description72
dc.description147
dc.description159
dc.descriptionConselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq/Brazil) [304727/2014-8, 142278/2013-0, 477692/2012-5]
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.languageEnglish
dc.publisherPergamon-Elsevier Science LTD
dc.publisherOxford
dc.relationComputers & Operations Research
dc.rightsfechado
dc.sourceWOS
dc.subjectSports Scheduling
dc.subjectTraveling Umpire Problem
dc.subjectInteger Programming
dc.subjectBranch-and-cut
dc.subjectOr In Sports
dc.titleLower Bounds For Large Traveling Umpire Instances: New Valid Inequalities And A Branch-and-cut Algorithm
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución