% This file was created with JabRef 2.5.
% Encoding: Cp1252
@ARTICLE{Irnich2010218,
author = {Stefan Irnich},
title = {A new branch-and-price algorithm for the traveling tournament problem},
journal = {European Journal of Operational Research},
year = {2010},
volume = {204},
pages = {218 - 228},
number = {2},
abstract = {The traveling tournament problem (ttp) consists of finding a distance-minimal
double round-robin tournament where the number of consecutive breaks
is bounded. For solving the problem exactly, we propose a new branch-and-price
approach. The starting point is a new compact formulation for the
ttp. The corresponding extensive formulation resulting from a Dantzig-Wolfe
decomposition is identical to one given by Easton, K., Nemhauser,
G., Trick, M., 2003. Solving the traveling tournament problem: a
combined interger programming and constraint programming approach.
In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of
Automated Timetabling IV, Volume 2740 of Lecture Notes in Computer
Science, Springer Verlag Berlin/Heidelberg, pp. 100-109, who suggest
to solve the tour-generation subproblem by constraint programming.
In contrast to their approach, our method explicitly utilizes the
network structure of the compact formulation: First, the column-generation
subproblem is a shortest-path problem with additional resource and
task-elementarity constraints. We show that this problem can be reformulated
as an ordinary shortest-path problem over an expanded network and,
thus, be solved much faster. An exact variable elimination procedure
then allows the reduction of the expanded networks while still guaranteeing
optimality. Second, the compact formulation gives rise to supplemental
branching rules, which are needed, since existing rules do not ensure
integrality in all cases. Third, non-repeater constraints are added
dynamically to the master problem only when violated. The result
is a fast exact algorithm, which improves many lower bounds of knowingly
hard ttp instances from the literature. For some instances, solutions
are proven optimal for the first time.},
doi = {DOI: 10.1016/j.ejor.2009.10.024},
issn = {0377-2217},
keywords = {Timetabling},
url = {http://www.sciencedirect.com/science/article/B6VCT-4XKHD9G-3/2/0d4a1951732b87cd8d98c47930f2c1dc}
}
@TECHREPORT{Irnich2009a,
author = {Stefan Irnich},
title = {A New Branch-and-Price Algorithm for the Traveling Tournament Problem},
institution = {Chair of Logistics Management, Mainz School of Management and Economics,
Johannes Gutenberg University},
year = {2009},
type = {Technical Report},
number = {LM09-01},
address = {Mainz},
month = {October}
}