-

 

 

 




Optimization Online





 

Improved Bounds for the Traveling Umpire Problem: A Stronger Formulation and a Relax-and-Fix Heuristic

Lucas de Oliveira (lucas.oliveira***at***ic.unicamp.br)
Cid de Souza (cid***at***ic.unicamp.br)
Tallys Yunes (tallys***at***miami.edu)

Abstract: Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often. We strengthen a known integer programming formulation for the TUP and use it to implement a relax-and- fix heuristic that improves the quality of 24 out of 25 best-known feasible solutions to instances in the TUP benchmark. We also improve all best-known lower bounds for those instances and, for the fi rst time, provide lower bounds for instances with more than 16 teams.

Keywords: OR in sports, heuristics, integer programming, relax-and-fix

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: Lucas de Oliveira, Cid C. de Souza, Tallys H. Yunes: Improved bounds for the traveling umpire problem: A stronger formulation and a relax-and-fix heuristic. European Journal of Operational Research 236(2): 592-600 (2014). DOI: 10.1016/j.ejor.2013.12.019

Download:

Entry Submitted: 08/28/2013
Entry Accepted: 08/29/2013
Entry Last Modified: 08/07/2014

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society