Two exact algorithms for the traveling umpire problem

Li Xue, Zhixing Luo and Andrew Lim

European Journal of Operational Research, 2015, vol. 243, issue 3, 932-943

Abstract: In this paper, we study the traveling umpire problem (TUP), a difficult combinatorial optimization problem that is formulated based on the key issues of Major League Baseball. We introduce an arc-flow model and a set partition model to formulate the problem. Based on these two models, we propose a branch-and-bound algorithm and a branch-and-price-and-cut algorithm. The branch-and-bound algorithm relies on lower bounds provided by a Lagrangian relaxation of the arc-flow model, while the branch-and-price-and-cut algorithm exploits lower bounds from the linear programming relaxation of the set partition model strengthened by a family of valid inequalities. In the branch-and-price-and-cut algorithm, we design an efficient label-setting algorithm to solve the pricing problem, and a branching strategy that combines three different branching rules. The two algorithms are tested on a set of well-known benchmark instances. The two exact algorithms are both able to rapidly solve instances with 10 teams or less, while the branch-and-price-and-cut algorithm can solve two instances with 14 teams. This is the first time that instances with 14 teams have been solved to optimality.

Keywords: Umpire scheduling; Lagrangian relaxation; Column generation; OR in sports; Mathematical model (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171401056X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:243:y:2015:i:3:p:932-943

DOI: 10.1016/j.ejor.2014.12.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().