Two exact algorithms for the traveling umpire problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 932-943 |
Journal / Publication | European Journal of Operational Research |
Volume | 243 |
Issue number | 3 |
Online published | 30 Dec 2014 |
Publication status | Published - 16 Jun 2015 |
Link(s)
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.
In: European Journal of Operational Research, Vol. 243, No. 3, 16.06.2015, p. 932-943.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review