Decorreu, no último ano, mais uma edição da International Timetabling Competition que reúne investigadores dos quatro cantos do mundo desafiados a resolver problemas complexos de escalonamento de horários. Aquela que foi a 4.ª edição da competição contou com a participação de investigadores e entusiastas de 57 países, sendo que apenas 15 equipas conseguiram resolver as instâncias da competição, entre as quais se encontra a equipa de investigadores do Técnico/ INESC-ID.

A equipa composta pelo aluno de doutoramento Alexandre Lemos e pelos seus orientadores, o professor Pedro Monteiro e professora Inês Lynce, ambos docentes do Departamento de Engenharia Informática (DEI), conseguiu arrecadar 79 pontos e assim atingir o top 5. Nos lugares cimeiros da tabela classificativa, além do grupo de portugueses, estão também investigadores da Dinamarca, França, Suíça e Kosovo. O grande desafio desta competição era escalonar os horários de grandes universidades com um conjunto muito variado de caraterísticas e restrições.

O que torna este posicionamento mais impressionante e “recompensador” é o facto de a equipa só ter entrado a meio da competição. A equipa do Técnico/INESC-ID já tinha, no passado, participado em competições semelhantes de onde saíram medalhados, “mas esta competição foi uma nova conquista”, frisa a professora Inês Lynce. “Habitualmente a fasquia é muito alta, o que justifica que acabem por não participar tantas equipas como se poderia imaginar. Nesta competição foram sendo disponibilizados exemplos ao longo do tempo, cada vez mais competitivos”, declara a docente.  A equipa portuguesa começou por ter dificuldade em resolver até os mais simples, mas a pouco e pouco foi fazendo progressos, acabando por oficializar a participação.  “A verdade é que alcançámos o cume da montanha, mas foi necessário ir subindo aos poucos. Foi uma verdadeira prova de resistência, com muita resiliência ao longo de vários meses”, declara a professora Inês Lynce.

A equipa assume a satisfação e orgulho com esta vitória, e com “o nível que a ferramenta desenvolvida por nós, a UniCorT, atingiu em tão pouco tempo de desenvolvimento”. “Temos um sentimento de sucesso depois de um arranque incerto, pois, no início só resolvíamos as instâncias exemplo. Depois desse choque inicial, não era trivial prever que iríamos conseguir resolver todas as instâncias e muito menos obtermos resultados com tanta qualidade”, recorda Alexandre Lemos.

De acordo com o aluno de doutoramento,“a grande dificuldade desta competição está no tamanho das instâncias fazendo com que o espaço de procura fique tão grande que não possa ser percorrido completamente num computador”. Assim, a chave do sucesso da equipa do Técnico “foi desenvolver diversas técnicas de pré-processamento que pudessem reduzir o espaço de procura e facilitar o trabalho do algoritmo de escalonamento”.

As instâncias da competição, ou seja, os problemas a revolver na International Timetabling Competition, foram extraídas de 10 instituições de ensino superior de 9 países diferentes espalhados por 5 continentes, sendo por isso, bastante distintas. “Essa diversidade implica que cada instância tenha as suas próprias características e restrições. Por isso, um dos grandes desafios foi encontrar uma abordagem que conseguisse encontrar uma solução de boa qualidade para todo o tipo de instâncias”, evidencia Alexandre Lemos. “O tamanho das instâncias também dificultava a utilização de abordagem padrão. E ao contrário do caso do Técnico na competição as aulas são escaladas em intervalos de 5min. Por isso a atribuição de uma aula para às 8:00 ou para 8.05 corresponde a soluções diferentes”, partilha ainda o elemento da equipa vencedora.

Para resolver os desafios da competição e singrar na mesma é preciso saber conceptualizar, formalizar o problema e naturalmente programar. “Conceptualização e formalização são muito importantes já que sem essas competências não conseguimos perceber com podemos ‘atacar’ o problema”, destaca Alexandre Lemos. “A formalização permite-nos perceber como podemos partir o problema de modo a ficar mais pequeno sem perder soluções. Considerando que o processo tem de ser automático também é importante saber programar, de modo a desenvolver uma ferramenta que gira a memória o mais eficientemente possível”, adiciona ainda o aluno de doutoramento.

Questionado sobre o facto de a ferramenta UniCorT criada pela equipa para esta competição pode ser adaptada à realidade do Técnico e servir de reforço à capacidade de escalonamento de horários da escola ou até mesmo da Universidade de Lisboa, Alexandre Lemos explica que a mesma “teria de ser adaptada às especificidades do problema do Técnico/ULisboa e às suas restrições”. Não tenho dúvidas que uma adaptação podia ser feita com sucesso a todos esses problemas. Talvez aconteça no futuro”, declara o aluno.

Embora a competição já tenha acabado, o trabalho prossegue e os resultados são continuamente comparados na comunidade científica no site da competição. Até à data, a equipa do Técnico/INESC já conseguiu arrecadar mais 89 pontos.