Orador: Jorge Paulo Jesus Santos. Data, hora e local: 10 de Outubro de 2014, início às 16h na sala de reuniões do Departamento de Matemática.
Resumo: Desde cedo que a humanidade se tem confrontado com problemas de partição territorial colocados em contextos diversos, nomeadamente na formação de círculos eleitorais, atribuição de zonas a vendedores, definição de zonas de tarifação de transportes públicos, afetação de áreas a centros escolares, etc. Este é um exemplo de um problema, entre outros, que pode ser modelado através de um grafo, transformando a partição dum território na partição dum grafo. O objetivo deste seminário é fazer uma apresentação de alguns modelos de Programação Linear que permitem a partição dum grafo em subgrafos. A formação de subgrafos é normalmente feita com base em critérios/restrições próprios de cada problema. Uma das restrições comuns a muitos dos problemas traduz-se pela imposição de subgrafos conexos. Só muito recentemente é que surgiram na literatura formulações da conexidade dos subgrafos em Programação Linear. Serão discutidas formulações existentes na literatura, bem como formulações alternativas. Serão ainda apresentados alguns resultados computacionais para avaliar a eficiência dos diferentes modelos.

Seminário realizado com o apoio do Centro de Matemática – 212 (Pest-OE/MAT/UI0212/2014).