The hardness of a problem has nothing to do with the intellectual effort required to find a solution.
Original posting: https://www.linkedin.com/pulse/hard-easy-problems-sports-competition-planning-arjen-schoneveld/
The field of sports competition planning consists of several interesting optimisation- and scheduling problems. For large recreational competitions with hundreds or even thousands of teams, officials and venues, these problems become difficult to solve and require clever algorithms. When asked about competition planning, the scheduling of matches on venues is probably the first planning problem that comes to your mind. However, In this post I will talk about two other optimisation problems, for the following reasons: first, I would like to highlight the difference between ‘easy’ and ‘hard’ problems in sports competition planning and second, because these optimisation problems are seemingly similar, as they both deal with the minimisation of travel distance.
The problems discussed are Pool Assignment and Official Assignment. Both pool assignment and official assignment aim to save travel time and costs. Pool assignment is concerned with the clustering of teams into pools or groups. The overall distance that the teams need to travel for their away matches should be as low as possible. On the other hand, Official assignment deals with assigning referees to a match. In this case, the overall distance that all officials combined need to travel from their homes to the match venue needs to be as low as possible.
The hardness of a problem has nothing to do with the intellectual effort required to find a solution. It has to do with the fact that it can take a lot of time for a computer to find the optimal solution.
It’s very common that two seemingly similar problems can be completely different from a computational perspective. A well known example of a “hard” distance minimisation problem is the “Travelling Salesperson Problem” (TSP). TSP is concerned with finding the shortest distance for a travelling salesperson between all cities that she needs to visit and in addition return to the same city from which she left. There is also the “Shortest Path Problem” (SPP). SPP is like TSP but the destination city and departure city are not the same, it’s a path from A to B not a loop from A to A like in TSP. SPP appears to be an “easy” problem that can be solved by Dijkstra’s algorithm.
Let’s return to the pool assignment problem. In recreational sports and especially in youth competitions the number of teams that are competing often exceeds the maximum number that can fit in a pool or a group. A pool size is typically between 10 and 14 teams for a full double competition, where “double” refers to the fact that both return matches have to be played.
In a typical dutch recreational football competition the number of registered teams can reach the 1000’s for a single competition class and age category. This means that 1000 teams need to be clustered into almost 100 pools. The total number of Dutch football teams (all age categories) exceeds 30.000.
Until some years ago the football association was performing this clustering manually, nowadays this process is fully automated, which saves them a significant amount of time. Another advantage is that the process of creating pools can be done much later in the overall competition planning process. As a consequence last minute team changes can be handled more easily, which improves the “user experience” for clubs.
It turns out that pool assignment is hard because of the “constraints” that we want to impose. The first constraint is the equal division of teams in groups. That is, groups need to be of equal size as much as possible. The second constraint states that the total travel time/distance between the teams' home venues as small as possible. Hence, teams that have their home venues close to each other will need to be put in the same pool as much as possible.
Finding minimum values for both total distance and group size deviation simultaneously makes Pool Assignment “hard”.
The algorithm that is used to solve pool assignment is a so-called approximation or heuristic method that is not exact, meaning that it will not necessarily find the best solution with the shortest overall travel distance. The algorithm balances computation time and quality of the solutions. An exact method can require years (!) of computation for just a few hundred teams.
Now, let’s consider the problem of assigning officials to a match. When assigning officials to a match usually one has to take into consideration the level of the official and the level of the match, this is a hard constraint. It’s simply an illegal assignment if the level of the official and the level of the match do not match (...). There are other hard constraints that we won’t consider because hard constraints, in this case, do not alter the hardness (!) of a problem.
Soft constraints can be a bit more complicated, they can include for example fairness principles. If an official is allowed to be assigned to matches of increasing level 1-3, typically it’s fair that every official in the same class gets an even distribution of matches in each of these levels. However, implementing this particular soft constraint is easy (from a computational efficiency perspective!), since it can be done by simple sort operations when assigning an official to a match.
Now let’s consider the minimisation of the total travel distance. Given a set of matches and their assigned officials the total travel distance is the cumulative distance of all the individual assignments. Typically, official assignment requires that the total travel time is minimised.
It follows that unlike pool assignment, official assignment is an easy optimisation problem.
Optimising the total travel time can be done using an efficient and exact algorithm, which means that the solution is always the most optimal solution that minimises the total travel time. In this case the algorithm that can be used is the so-called “Hungarian Algorithm”.
What I have shown is that two optimisation problems that stem from Sports Planning which are both dealing with minimisation of distance, have different “computational hardness”. pool assignment is an optimisation problem that is hard to solve by a computer in a reasonable time. We need to rely on an approximation algorithm in order to get the result in an acceptable time. Due to this compromise, the solution will not necessarily be the best solution.
On the contrary, the solution for official assignment can be found efficiently. As a consequence, the distance minimisation will be optimal, it will always find an official assignment with the least distance travelled.
