Lower bounds for large traveling umpire instances: New valid inequalities and a branch-and-cut algorithm |
| |
| Affiliation: | 1. Institute of Computing, University of Campinas (UNICAMP), Campinas, SP, Brazil;2. School of Business Administration, University of Miami, 5250 University Drive, Room KE405, Coral Gables, FL 33146, USA;1. Department of Economics and Management, University of Brescia, Brescia, Italy.;1. Department of Mechanical Engineering, Government Polytechnic, Jhajjar 124103, Haryana, India;2. Department of Mechanical Engineering, Graphic Era University, Dehradun 248002, Uttarakhand, India;3. Tianjin University of Technology, School of Management, Tianjin, PR China;4. Department of Engineering Systems and Management, Masdar Institute of Science and Technology, Abu Dhabi, United Arab Emirates;1. Pennsylvania State University, The Behrend College, Erie, PA 16563, USA;2. American University of the Middle East, Eqaila, Kuwait;1. Key Laboratory for Thermal Science and Power Engineering of Ministry of Education, Department of Energy and Power Engineering, Tsinghua University, Beijing 100084, China;2. Department of Mechanical Engineering, Johns Hopkins University, Baltimore, MD 21218, USA |
| |
| Abstract: | Given 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). |
| |
| Keywords: | Sports scheduling Traveling umpire problem Integer programming Branch-and-cut OR in sports |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
