Keywords

1 Introduction

Studies involving the application of Operational Research (OR) to sports began at almost the same time the discipline was officially created, historically accepted as the period of World War II. Examples of application range from problems such as scheduling competitions that respect minimum rest intervals for athletes [1], strategies involving decisions of when to attack or defend against certain teams; to selection of players that minimizes hiring costs while optimizing the chances of the hiring team being champion [2].

Several decision-making methods that involve subjective assessment and dependent on the decision-maker experience have been developed [3, 4], however, this work involves the development of a Binary Programming model aiming to maximize the number of games played by 31 players who signed up individually – i.e. they are not part of a team – to a program that offers 14 different soccer competitions.

The problem was identified by a Canadian sports event management company when it needed to allocate players to different competitions knowing that each player has restrictions on the days of the week they can participate in, skill level, size, and team mix. The company has to ensure that all registered players participate in at least one competition and that no player is allocated to two or more competitions that take place on the same day.

The model presented in this work was structured using Microsoft Excel and solved with the help of Solver developed by the company Frontline Solvers (www.solver.com), which is similar to the native option of MS Excel, but is able to support all variables and constraints of the present problem. The results of the application of the model were satisfactory, since, although not all competitions have the minimum number of players allocated to them, all players will participate in at least one competition.

2 Mathematical Programming

As stated in [5], a Binary Programming problem resembles a Linear Programming problem (in which the objective function and constraints are linear equations), with the difference that all decision variables should accept only the values 0 or 1. This binary characteristic of variables can be interpreted as “yes-no”, “open-do not open” or “choose-do not choose” decisions. The latter example represents the decision problem addressed in this work, which intends to allocate, or not, certain players to specific competitions.

As defined in [6], the following system of equations is an example of a general binary programming model:

$$ \mathit{\operatorname{Max}}\ or\min Z=f\left(x1,x2,\dots, xn\right)=c1x1+c2x2+\dots + cnxn $$

Subject to:

$$ {\displaystyle \begin{array}{c}a11x1+a12x2+\dots +a1 nxn\ \left\{\le, =,\ge \right\}\ b1\\ {}a21x1+a22x2+\dots +a2 nxn\ \left\{\le, =,\ge \right\}\ b2\\ {}\dots \\ {} am1x1+ am2x2+\dots + am nxn\ \left\{\le, =,\ge \right\}\ bm\\ {}x1,x2,\dots, xn\ge 0\\ {}x1,x2,\dots, xn\ binary\end{array}} $$

2.1 Operations Research in Sports

Although the application of mathematical tools for decision-making were already used long before World War II in various sectors of society (in fact there are precursor works of Operations Research (OR) dating back to the fifteenth century, according to [7]), that period is considered to be the era of the official emergence of OR. Great focus was given to the discipline at that time in order to optimize the allocation of scarce resources to soldiers and also assist in logistics decisions [8].

With the end of the war and the successful application of OR tools, professionals and universities began to focus their efforts both in applying the models already known as well as developing new models for solving civil problems, such as optimization of production mix, asset choices with greater profitability and even optimal location of facilities [8,9,10].

[8] explains that one topic under OR that has been massively studied in the past 60 years is the resource allocation problem, concerned with the optimal allocation of resources to specific activities in order to maximize productivity or minimize cost. The same authors also argues that the allocation problem can be seen in a variety of application areas, such as sales force allocation and portfolio selection.

As in other sectors that have limited resources and rely on well-founded strategic decisions to ensure economic viability, several organizations in the sports sector started to use optimization tools [11]. From firms involved in defining the best dates of football matches [12], the best strategic formation for a football team [13], sports marketing teams that need to optimize resource allocation for different advertising vehicles [14], strategy for changing tires in car racing [15], and even the best locations within a hockey rink for a player to score a goal [16].

The present work intends to apply a Binary Programming model for the allocation of players to different soccer competitions according to restrictions defined by the players themselves and others being characteristics of the competitions. This same modeling is widely used with several different objectives, such as allocating salespeople in different regions to maximize profit, identifying the ideal location to open a distribution centre so the logistics costs are minimized, among others [5].

2.2 Binary Programming and the Allocation Problem in Sports

Although apparently trivial, the allocation problem can become unmanageable without the use of an optimization model given the number of possible combinations between variables grows exponentially as those increase by one unit – such problems are called combinatorial optimization problems [17].

It is common to find allocation and scheduling studies involving sports in the literature, however most are concerned with scheduling of games at specific venues [18] and allocating games and players in ways to minimize tournament costs [19], rest duration differences between games [1], and group-strength fairness [20].

In this study, the authors are concerned with the formation of as many teams as possible by allocating players to different competitions with the objective of maximizing the number of competitions played by each player throughout the week.

3 Case Study

This section presents a case study referring to a Canadian sports event management company whose identified problem is intended to be solved with the application of a Binary Programming model.

In Canada, from mid-October until mid-March, low temperatures and snow make it difficult, when not impossible, to play sports outdoors, therefore many indoor multi-sports facilities are available to offer citizens the opportunity to play different sports during that period.

Although the number of facilities increase every year, it is challenging to accommodate everyone’s individual needs and preferences, which lead a few municipal-level organizations to setup specific competitions at certain indoor facilities in order to make it possible for most people to attend as many games/sports as they please. Participants can enroll in those competitions either as part of a team or individually (the latter meaning that the company is responsible for allocating each person to as many competitions as possible according to his/her availability and competitions’ constraints).

In this study, a company needs to allocate 31 individually enrolled players – including 19 men and 12 women – in 14 soccer competitions. Such competitions take place on different days (sometimes with more than one competition per day), are divided into 2 skill levels, co-ed (males and females in the same team) or 1-sex team, and number of players per team (Tables 1, 2 and 3). Tables 4 and 5 – in the Appendix – show the different characteristics of each competition, while Tables 1 and 2 identify the competitions in which each player can participate with the “Player x Competition” cell highlighted in blue and marked with an “x”, e.g., Man 1 can play all competitions, while Woman 1 can participate only in competitions 3 and 8.

Table 1 Men’s availability
Full size table
Table 2 Women’s availability
Full size table
Table 3 Model result
Full size table

3.1 Computational Implementation

For the construction of this problem, each player i (i = 1, …, 31), provided his/her availability to play competition j (j = 1, …, 14). As the model must choose whether player i participates in competition j, variable xij must be 1 or 0 – binary variable – where 1 indicates that player i participates in competition j, and 0 if it does not participate in that competition. In the case of a player i, who cannot play competition j, the variable xij will not be included in the model.

The objective function of the problem seeks the maximization of the number of players participating in competitions, therefore:

$$ \operatorname{Maximize}\ \mathrm{Z}=\sum xij $$
(1)

Subject to:

$$ \mathrm{xij}=0,\mathrm{i}=20,\dots, 31\ \mathrm{and}\ \mathrm{j}=10,11 $$
(2)
$$ \mathrm{xi}1+\mathrm{xi}13\le 1,\mathrm{i}=1,\dots, 31 $$
(3)
$$ \mathrm{xi}2+\mathrm{xi}10+\mathrm{xi}14\le 1,\mathrm{i}=1,\dots, 31 $$
(4)
$$ \mathrm{xi}3+\mathrm{xi}8\le 1,\mathrm{i}=1,\dots, 31 $$
(5)
$$ \mathrm{xi}4+\mathrm{xi}5+\mathrm{xi}11+\mathrm{xi}12\le 1,\mathrm{i}=1,\dots, 31 $$
(6)
$$ \mathrm{xi}6+\mathrm{xi}7+\mathrm{xi}9\le 1,\mathrm{i}=1,\dots, 31 $$
(7)
$$ \sum xij\ge 3,\mathrm{i}=1,\dots, 19\ \mathrm{and}\ \mathrm{j}=1,2,3,8,9,13,14 $$
(8)
$$ \sum xij\le 5,\mathrm{i}=1,\dots, 19\ \mathrm{and}\ \mathrm{j}=1,2,3,8,9,13,14 $$
(9)
$$ \sum xij\ge 5,\mathrm{i}=1,\dots, 19\ \mathrm{and}\ \mathrm{j}=4,5,6,7,12 $$
(10)
$$ \sum xij\le 6,\mathrm{i}=1,\dots, 19\ \mathrm{and}\ \mathrm{j}=4,5,6,7,12 $$
(11)
$$ \sum xij\ge 5,\mathrm{i}=1,\dots, 19\ \mathrm{and}\ \mathrm{j}=10,11 $$
(12)
$$ \sum xij\ge 2,\mathrm{i}=20,\dots, 31\ \mathrm{and}\ \mathrm{j}=1,\dots, 14 $$
(13)
$$ \sum xij\le 4,\mathrm{i}=20,\dots, 31\ \mathrm{and}\ \mathrm{j}=1,\dots, 14 $$
(14)
$$ \sum xij\ge 5,\mathrm{i}=1,\dots, 31\ \mathrm{and}\ \mathrm{j}=1,2,3,8,9,10,11,13,14 $$
(15)
$$ \sum xij\ge 7,\mathrm{i}=1,\dots, 31\ \mathrm{and}\ \mathrm{j}=4,5,6,7,12 $$
(16)
$$ \mathrm{xij}\ \mathrm{i}\mathrm{s}\ \mathrm{binary}\ \mathrm{for}\ \mathrm{all}\ \mathrm{i}\ \mathrm{and}\ \mathrm{j} $$
(17)
$$ \mathrm{i}=1,\dots, 31\ \mathrm{and}\ \mathrm{j}=1,\dots, 14 $$
(18)

The problem’s constraints are identified below:

  1. 1.

    The company’s goal is to get all enrolled players to participate in at least one competition (Eq. 1 above)

  2. 2.

    No woman can participate in competitions 10 and 11, as they are exclusive to men, so they are highlighted in gray in Fig. 1 (Eq. 2 above)

  3. 3.

    Players cannot be allocated in more than one competition on the same day (Eqs. 3, 4, 5, 6 and 7 above)

  4. 4.

    In competitions with teams of 5 players, at least 3 and maximum 5 must be men (Eqs. 8 and 9 above)

  5. 5.

    In competitions with teams of 7 players, at least 5 and maximum 6 must be men (Eqs. 10 and 11 above)

  6. 6.

    Competitions 10 and 11 must have at least 5 men allocated to each o them (Eq. 12 above)

  7. 7.

    Co-ed competitions must have a minimum of 2 and a maximum of 4 women per team (Eqs. 13 and 14 above)

  8. 8.

    A competition only takes place if there are at least 5 or 7 players per team, according to the characteristic of the competition (Eqs. 15 and 16 above)

  9. 9.

    Every variable xij is binary, i.e., its value must be either 0 or 1 (Eq. 17 above)

Figure 1 – in the Appendix – shows the structure of the problem created in MS Excel, which has a total of 202 variables, 139 of which are associated with male players and 63 with female players, and 193 constraints.

3.2 Results

The Binary Programming model presented in the previous section, with all its constraints, does not have a possible solution, since the following cannot be respected:

  • Allocate at least 3 men in Competition 9

  • Allocate at least 5 men in Competitions 10 and 11

  • Allocate at least 5 men in Competition 12

Thus, the authors chose to relax such constraints, that is, to exclude them from the model, and rerun it, which allowed the resolution of the problem and an optimal result for the new scenario was found. However, due to the relaxation of the previous constraints, the solution found cannot allocate enough players to Competitions 9, 10, 11 and 12. All other competitions had enough players allocated to them and the goal of allocating each player to at least one competition has been met (all players will participate in at least 1 competition and a maximum of 5 competitions). In addition, all other constraints have been respected.

Table 3 shows the competitions each player had availability to play highlighted in blue, similar to Tables 1 and 2, and also which competition each of them will be actually playing – 1 – and which they will not – 0 – as determined by the binary programming model. The table also shows, in the rightest column, the number of competitions per week each player was assigned to. Note that competitions 9, 10, 11 and 12 have been removed.

4 Conclusion

The use of an optimization model for the studied scenario can be considered successful, given the main objective was achieved in a timely manner. Due to the constraints associated with the competitions’ rules, the prosed model could not find a solution that allocated enough players to all competitions, but the main goal – allocating every player to at least 1 competition – was achieved.

If the company in question had chosen to find the optimal solution manually, it should have worked with a number of possibilities in the order of 2n, where n is the number of variables, therefore in the order of 2202 = 6.43 × 1060 possibilities (without taking the constraints into account). In addition, there are companies responsible for defining calendars and allocating resources for major events and professional leagues, where variables can reach tens of thousands, making the problem impossible to solve without the application of an optimization model, such as that presented in this paper.

Although not in the scope of this work, therefore not a variable included in the optimization model, profit increase can be considered a secondary benefit of the application of the proposed model insofar as all players pay an enrollment fee to participate in the competitions, thus, the more players allocated, the higher the profit.

It should be noted that the model presented in this study is a proposal of an initial model, with the possibility of further studies to implement improvements according to operational needs. The methodology proposed in this paper can, however, be applied to the most diverse problems of the public, private or military sectors.