A branching scheme based on First-Break-Then-Schedule decomposition

Dirk Briskorn, Andreas Drexl

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home-away-pattern sets having the minimum number of breaks. An branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.

MoreLess

Year of publication:	2007
Authors:	Briskorn, Dirk ; Drexl, Andreas
Publisher:	Kiel : Inst. f. Betriebswirtschaftslehre
Subject:	Sports league scheduling \| round robin tournaments \| home-away-pattern set \| break \| branch-and-bound \| Round robin tournaments \| Sport \| Sports \| Scheduling-Verfahren \| Scheduling problem \| Branch-and-Bound \| Branch and Bound \| Theorie \| Theory