I am a big fan of football, or soccer (depending on what part of the world you are from). I have played the game for most of my life. In addition to being a player, I was also the coach, or manager, of my team while I was living in Sydney. It is during this time as coach that I decided to come up with a model to find the optimal interchange schedule.
Just putting it out there straight away, I applied optimisation to a problem that really did not require optimisation techniques. I was in the middle of my PhD and I was really excited about what you can apply integer programming to, so I thought I would try using integer programming to help with my coaching. Also, I was asked to give a seminar to our post graduate group in the mathematics department at UNSW, with the mandate that is it supposed to be fun. So the application of optimisation to find a football interchange schedule seemed like a great topic to discuss.
Just to give a little background to this situation. First, it was not a normal football match. I was managing my team in a 7-a-side tournament, which consisted of multiple games on the one day. Second, for this particular series of matches the interchange of players, as opposed to substitution, was used. This meant that I could put players on and off the field constantly throughout the game. Third, in terms of performance, I was not the best coach. I usually prioritised fairness of time on the pitch over the strength of the team. So I would always try to give each play an equal amount of time on the field. It is this latter part that sparked the idea of using optimisation to manage my football team. Finally, the idea of using optimisation to help with my coaching really fits with my desire to apply optimisation everywhere, as I have shown with the teacher scheduling problem that I previously worked on.
Something that really made it difficult for me was that the tournament we were playing in was a knock-out from the second round. So my team would at least play two games, more likely it was going to be exactly two games. Given that the games only ran for 20 minutes, I didn’t want my players to come along to the tournament to spend only a couple of minutes of the field. So I tried to find a way to may it fair for everyone.
More formally, the details of the problem are:
- We were playing in a 7-a-side tournament, with a maximum of 12 players on the team. It was my decision to utilise the full 12 players in both games.
- Each match consisted of two 10 minute halves.
- We were only going to play 2 games. I made this assumption because if we happen to play more than 2, then my optimal interchange schedule no longer mattered. I could just put on my best team after that.
- The formation was the following and I had players that were specialists in particular positions. So I wanted to keep those players in their best positions, especially the goal keeper
In addition to the formation, the data that I had was related to the players and the positions that they preferred. I grouped the positions into goal keeper, back, midfield and forward. So I had data that looked something like:
- Josh: forward, midfield
- Simon: forward
- James: midfield, back
- Brad: goal keeper, back
- Steve: back
- Charlie: midfield, back
- Toby: forward, midfield
- Jack: midfield
- Tim: midfield, back
- Sam: forward
- Adam: goal keeper, forward
- Tony: back
The optimisation problem
As I said earlier, I wanted to give everyone an equal amount of playing time. This is what is described as fairness. Unfortunately, fairness is a concept that is quite difficult to define and there has not been any consensus on how we should model fairness. But anyway, I thought that equal playing time was a good measure. To make this problem easier, I did not treat time as continuous. The reason for this was that I did not want to have players running on and off the field constantly throughout the game. So I discretised the time into 3 minute blocks. That meant there were two interchanges per half of the game.
As a technical note: discretisation of time is a method that is commonly used when applying optimisation techniques, particularly integer programming. One of the reasons for this is that a lot of integer programming applications focus on discrete values, such as one person, one vehicle, one delivery, and so on. So discretisation makes time fit into the framework used for other parts of the model. Also, it is easier to conceptualise and model when you have discrete time points, instead of a continuous period.
The optimisation problem that I wanted to solve can be described by:
- Minimise the sum of the deviation of the each player’s actual playing time to the average playing time (This is how I measured fairness).
- Subject to:
- the players can only play in their preferred positions.
- the formation must be respected in each time period. Exactly 2 backs, 3 midfield and 1 forward are assigned in each time period (the goal keeper was kept constant for a full half).
This is a very simple problem to formulate. However, it is not as easy to solve. The issue with solving this problem is that there is a lot of symmetry (many solutions have the same objective value), making it difficult to prove the optimal solution.
Did it actually work?
I came up with this model the day of our first time playing in the tournament. I was trying to work out an “optimal” interchange schedule by hand, but then realised that this could be easily formulated as an optimisation problem. Unfortunately I didn’t get to use the model that time. However, we did enter this tournament the following year. By then I had given my post graduate seminar and also wrote the software to solve this problem. So I got the opportunity to test the solution in real time.
The short answer to the above questions is: NO. One of the biggest issues is that in a 7-a-side tournament, people get tired very quickly. Also, we were not very fit. There was a tendency to ask for a change before the allotted time in my schedule had elapsed. In order for this plan to be most effective, I needed people to be less like people and more like machines and blindly follow the plan. Once the first change was made out of schedule (which happened in matter of minutes), then the whole plan fell apart. We didn’t have a recovery plan in place, and the optimisation model was not being resolved in real time.
The end result was that people didn’t really care how much time that they got, mainly because everyone got tired and they all got a “fair” amount of time anyway. We did not make it past the second game.
Would I do it again?
Given the failure of the implementation of the model, I would be natural to think that it was not worthwhile. However, I think that it has been a great success. It did not work as planned, but it was a great example of an optimisation problem in the real world.