Minimizing costs in round robin tournaments with place constraints

In this paper we consider a general sports league scheduling problem and propose solution algorithms for it. The objective is to find a feasible schedule for a round robin tournament with minimum number of breaks and minimum total costs where additionally place constraints are taken into account. We present a “first-break, then-schedule” approach which uses an enumerative procedure to generate home-away patterns and integer programming for finding corresponding schedules. Computational results are presented for leagues with up to 14 teams.     

IP models for round robin tournaments

Generally speaking in sports competition a number of teams play against each other over a period of time according to a certain scheme. The round robin scheme is very popular in many team sports like soccer and basketball. In this paper we study several basic variants of round robin tournaments. Additionally, we examine real world issues that have to be considered when constructing a sports league schedule. We consider constraints imposed by third parties such as security aspects and legal requirements. Moreover, we analyze constraints aiming at attractive and fair sports league schedules. Throughout this paper integer programming models are the means to formally define what the particular problem under consideration is all about. Moreover, the standard solver Cplex is used in order to compute optimal solutions for small- to medium-size instances. Computational results indicate which particular constraint to relax in order to come up with acceptable schedules in reasonable time.     

A Lagrangian approach for minimum cost single round robin tournaments

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 match and period. Since matches are carried out at one of the both opponents venues matches may be forbidden in certain periods due to unavailability of stadiums. The goal is to find a minimum cost tournament among those having no match scheduled infeasible. We employ a Lagrangian relaxation approach in order to obtain tight lower bounds. Moreover, we develop a cost-oriented repair mechanism yielding a feasible tournament schedule to each solution of the relaxed problem.     

Sports tournament scheduling to determine the required number of venues subject to the minimum timeslots under given formats

We studied a two-phase, preliminary and finals, tournament, which commonly adopted for non-professional sports. The round robin tournament in divisions is played in the preliminary phase, followed by one of the three variants, namely single elimination, double elimination, and round robin in the finals phase. The objective is to determine the required number of venues (tables or courts) subject to the least timeslots under the given format. We used a diagonal symmetric matrix to pair teams to games and to schedule games in timeslots for the round robin tournament. For the preliminary phase, we proposed a procedure to find the number of divisions and the number of teams in each division that minimize the total number of games and timeslots accordingly. For the finals phase, we determined the number of venues required in the least timeslots. We then formulated a constraint programming model based on the diagonal symmetric matrix for the round robin tournament. Finally, we provided suggestions for choosing the appropriate competition format.     

A heuristic for minimizing weighted carry-over effects in round robin tournaments

The carry-over effects value is one of the various measures one can consider to assess the quality of a round robin tournament schedule. We introduce and discuss a new, weighted variant of the minimum carry-over effects value problem. The problem is formulated by integer programming and an algorithm based on the hybridization of the Iterated Local Search metaheuristic with a multistart strategy is proposed. Numerical results are presented.     

A bracket assignment problem for the National Collegiate Athletic Association Men's Basketball Tournament

The National Collegiate Athletic Association Men's Basketball Tournament is a 65‐team championship in American college basketball, in which a single team is eliminated in a play‐in game, followed by a six‐round, single‐elimination tournament. Owing to its immense popularity, each aspect of the tournament, including the selection of teams, their ranking (or “seeding”), and the assignment of teams to locations for the first few rounds, is a hotly debated topic. In this paper, we concentrate on the latter aspect of the tournament composition, as the first two elements have been extensively researched in a variety of settings. We formulate the team assignment problem as a mixed‐integer program, and examine various methods of tightening the linear programming relaxation in order to yield an effective methodology for generating feasible tournament pairings with minimum expected travel. Finally, we demonstrate the results of our algorithm on data derived from the 2004 and 2005 basketball tournaments.     

The traveling tournament problem with predefined venues

Sports scheduling is a very attractive application area not only because of the interesting mathematical structures of the problems, but also due to their importance in practice and to the big business that sports have become. In this paper, we introduce the Traveling Tournament Problem with Predefined Venues, which consists in scheduling a compact single round robin tournament with a predefined venue assignment for each game (i.e., the venue where each game takes place is known beforehand) while the total distance traveled by the teams is minimized. Three integer programming formulations are proposed and compared. We also propose some simple enumeration strategies to generate feasible solutions to real-size instances in a reasonable amount of time. We show that two original enumeration strategies outperform an improvement heuristic embedded within a commercial solver. Comparative numerical results are presented.     

Scheduling the Italian Football League: an ILP-based approach

Scheduling the Italian Major Football League (the so-called “Serie A”) consists in finding for that league a double round robin tournament schedule that takes into account both typical requirements such as conditions on home-away matches and specific requests of the Italian Football Association such as twin-schedules for teams belonging to the same home-town. In this paper, we present a solution procedure able to derive feasible schedules that are also balanced with respect to additional cable televisions requirements. This procedure adapts the recent approach by Nemhauser and Trick to schedule a College Basketball Conference that considers however only half of the teams involved here. The proposed procedure is divided into three phases: phase 1 generates a pattern set respecting the cable televisions requirements and several other constraints; phase 2 produces a feasible round robin schedule compatible with the above pattern set; finally, phase 3 generates the actual calendar assigning the teams to the patterns. The procedure allows to generate within short time several different reasonable calendars satisfying the cable television companies requirements and satisfying various other operational constraints while minimizing the total number of violations on the home-away matches conditions.     

Scheduling Sport Tournaments using Constraint Logic Programming

We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is an assignment problem and it is solved using a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language \eclipse. Experimental results show that, in practical cases, the optimal solution of the assignment problem (which is not necessarily optimal for the overall problem) can be found in reasonable time, despite the fact that the problem is NP-complete. In addition, a local search procedure has been developed in order to provide, when necessary, an approximate solution in shorter time.     

Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) [8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) [14].     

一种基于触发机制的轮转算法

在负载平衡技术中,必须使用合适的算法进行成员选择,以决定由哪个副本对象处理到来的客户请求。传统轮转负载平衡算法只能在某些特定条件下平衡负载。针对该缺点,结合普通轮转算法和加权算法的优点,提出一种基于触发机制的轮转算法。实验结果表明,该算法能感知后段资源。     

Survivable network design: the capacitated minimum spanning network problem

We are given an undirected graph G=(V,E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r∈V. In this paper, we consider the capacitated minimum spanning network (CMSN) problem, which asks for a minimum cost spanning network such that the removal of r and its incident edges breaks the network into a number of components (groups), each of which is 2-edge-connected with a total weight of at most k. We show that the CMSN problem is NP-hard, and present a 4-approximation algorithm for graphs satisfying triangle inequality. We also show how to obtain similar approximation results for a related 2-vertex-connected CMSN problem.     

A set partitioning based goal programming model for the team formation problem

In this paper, we offer a multi-objective set-partitioning formulation for team formation problems using goal programming. Instead of selecting team members to teams, we select suitable teams from a set of teams. This set is generated using a heuristic algorithm that uses the social network of potential team members. We then utilize the proposed multi-objective formulation to select the desired number of teams from this set that meets the skill requirements. Therefore, we ensure that selected teams include individuals with the required skills and effective communication with each other. Two real datasets are used to test the model. The results obtained with the proposed solution are compared with two well-known approaches: weighted and lexicographic goal programming. Results reveal that weighted and lexicographic goal programming approaches generate almost identical solutions for the datasets tested. Our approach, on the other hand, mostly picks teams with lower communication costs. Even in some cases, better solutions are obtained with the proposed approach. Findings show that the developed solution approach is a promising approach to handle team formation problems.     

一种新型的网络包公平调度算法的研究*

针对现有分组轮转法的局限,提出一种新的分组策略——虚拟权重队列分组策略。在这个新的分组策略的基础上,结合DRR和WF2Q,提出了虚拟权重队列分组轮转法。仿真实验表明,虚拟权重队列分组轮转调度算法比现有的分组轮转法拥有更好的延时性能和公平性能。     

A field study of developer pairs: productivity impacts and implications

Pair programming purportedly delivers quality code with little productivity loss. The authors' field study, outside the pair programming environment, shows that two-person teams working independently are more productive than those working concurrently; agile methods may overcome inherent productivity losses of concurrent development. This research contrasts starkly with our field study findings. We decided to reexamine our earlier productivity data from teams of two and ask: Would our previous findings of concurrent-work productivity loss be reversed if we look only at programming pairs rather than teams of all sizes? If so, we could conclude that pairs are naturally more productive than larger teams, regardless of the collaborative process. If not, we could conclude that the collaboration mechanisms prescribed in pair programming might overcome a natural loss of productivity from concurrent work. We offer these findings and their implications as a benchmark against which we might measure the potential of pair programming practices.     

An adaptive and innovative question-driven competition-based intelligent tutoring system for learning

ISCARE (Information System for Competition based on pRoblem solving in Education) is a new and innovative intelligent tutoring system that we have designed and implemented. This tool allows the competition among students for improving their learning process in a course. The tool takes some ideas from the Swiss-system widely used in chess and adapts them to the educational area. The competition is based on different tournaments and rounds. In each round, students are assigned in pairs of two, which compete one against another, and each pair receives different questions that students have to solve in a limit of time. Students can see their partial ratings after each round and their final rating after a tournament. A lot of knowledge from different disciplines was used to design, and implement this system, as ISCARE includes different functionality such as the students’ registration into the system, the creation of tournaments, the registration and assignment of students to tournaments, the management of each tournament life cycle (started, in execution, finished, etc.), the addition of the different exercises to tournaments, the calculation of pairs of students for each round with different algorithms, the assignment of exercises per round and pair, the scorings of the students per round and tournament, the management of the students’ ratings, or the visualization of information. This paper presents the ISCARE intelligent tutoring system, describing its different options, menus, or functionality as well as its architecture and the specific modeling to achieve the desired features.     

基于节点分组的异构集群负载均衡算法*

首先根据排队论理论给出了一个理想的负载均衡模型。针对该模型的系统开销问题,提出了一种基于节点分组的异构集群负载均衡算法。实验结果表明,相比于轮转法和加权轮转法这两种普遍采用的负载均衡算法,该算法可以提供更加稳定的请求响应时间,并在负载波动较大时明显提高集群的吞吐率。     

Designing a fine‐grained parallel differential evolution with Pareto tournaments for solving an optical networking problem

The future of designing optical networks focuses on the wavelength division multiplexing technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of optical fiber. However, when it is required to establish a set of demands, a problem comes up. This problem is known as routing and wavelength assignment problem. In this work, we have tackled the static routing and wavelength assignment problem by using multiobjective evolutionary computing. The algorithm applied is the differential evolution but modified with the Pareto tournaments concept for being adapted to the multiobjective context. By using OpenMP, an application programming interface that supports multiplatform shared memory multiprocessing programming, we have demonstrated that this algorithm is highly suitable to be parallelized. We have performed several experiments in multicore systems with two, four, and eight cores, obtaining 97.57% of mean efficiency. To ensure that our heuristic obtains relevant results, we have compared it with a parallel version of the standard fast nondominated sorting genetic algorithm. Finally, in order to show the goodness and effectiveness of the differential evolution with Pareto tournaments algorithm when dealing with this problem, we present diverse multiobjective comparisons with the nondominated sorting genetic algorithm and other approaches published in the literature. Copyright © 2013 John Wiley & Sons, Ltd.     

New models for the Mirrored Traveling Tournament Problem

The Mirrored Traveling Tournament Problem (mTTP) is a challenging combinatorial optimization problem which consists in generating a timetable for sports tournaments with two half series, what is equivalent to a double round-robin timetable problem. The distance traveled by the teams should be minimized in the final timetable, and a new objective is to minimize the longest distance traveled, named MinMaxTTP. It is proposed an integer programming formulation to the mTTP and two models with dynamic constraints to its solution. Both models are based on the detection of independent sets on conflict graphs, whose use has not been reported in the literature about the problem. Real data benchmarks from a baseball tournament are used in the experiments carried out.     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.