Two exact algorithms for the traveling umpire problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

14 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)932-943
Journal / PublicationEuropean Journal of Operational Research
Volume243
Issue number3
Online published30 Dec 2014
Publication statusPublished - 16 Jun 2015

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.

Research Area(s)

  • Column generation, Lagrangian relaxation, Mathematical model, OR in sports, Umpire scheduling

Citation Format(s)

Two exact algorithms for the traveling umpire problem. / Xue, Li; Luo, Zhixing; Lim, Andrew.
In: European Journal of Operational Research, Vol. 243, No. 3, 16.06.2015, p. 932-943.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review