Another edition of the International Timetabling Competition took place last year. This competition brings together researchers from all over the world, who are challenged and motivated to further research on complex university course timetabling problems coming from practice. Researchers and enthusiasts from 57 countries attended the 4th edition of the competition. Only 15 teams, including Técnico/INESC-ID team, were able to tackle the competition’s instances.
The team composed of PhD student Alexandre Lemos and his supervisors, Pedro Monteiro and Inês Lynce, both professors at the Department of Computer Science and Engineering (DEI/IST), managed to achieve 79 points and reach the top 5. At the top of the list, besides the Portuguese team, there are also researchers from Denmark, France, Switzerland and Kosovo.
What makes this positioning more impressive and “rewarding” is the fact that the team entered halfway through the competition. The Técnico / INESC-ID team had already won several medals in previous similar competitions, “but this competition was a new achievement”, highlights professor Inês Lynce. “Usually the competition sets a very high standard, which leads that only a few teams are able to participate. In this competition, increasingly competitive examples have been made available over time”, she adds. “The Portuguese team started having difficulty solving even the simplest ones, but gradually the team was able to make progress, ending up making their participation official. “The truth is that we reached the top of the mountain, but it was necessary to go up gradually. It was a true test of our strength, which involved a lot of resilience over several months ”, says professor Inês Lynce.
The team members are happy and proud of this victory, namely “the tool we developed – UniCorT. In the beginning of the competition, we were only capable of solving the early instances. After that initial shock, we couldn’t imagine that we would be able to tackle all instances and get excellent results”, recalls Alexandre Lemos.
The competition instances, that is, the problems to be solved, were extracted from 10 higher education institutions, of 9 different countries across 5 continents. “This diversity implies that each instance has its own characteristics and restrictions. Therefore, one of the great challenges was to find an approach that could find a good quality solution for all types of instances”, highlights Alexandre Lemos. “The size of the instances also made it difficult to use the standard approach. In the competition, unlike Técnico, classes are scheduled at 5-minute intervals. That is why a class assignment for 8:00 or 8.05 presupposes the adoption of different solutions”, he adds.
In order to solve the challenges of the competition, it is necessary to know how to design, formalize the problem and programming. “Conceptualization and formalization are very importante to tackle the problem”, highlights Alexandre Lemos. “Formalization allows us to understand how we can break the problem down so that it gets smaller without losing solutions. Considering that the process has to be automatic, it is also important to know how to program, in order to develop a tool that turns the memory as efficiently as possible ”, adds the PhD student.
Asked if UniCorT tool could be adapted to Técnico or even to Universidade de Lisboa, Alexandre Lemos explains “it would have to be adapted to the specific Técnico / ULisboa’s problems and restrictions. I have no doubt that a successful adaptation could be done to all these problems. Maybe it will happen in the future”, says the student.
Although the competition is over, the work continues and the results are continuously compared on ITC website. To date, the Técnico / INESC team has managed to get another 89 points.
