Operations Research Seminar - 27/5/2015

Wednesday, 27 May 2015, 3:15 p.m.

Lecturer: Teresa Almeida, ISEG, ULisboa & CMAF-CIO

Title: "k-Clube Triangular - modelos de PLI e desigualdades válidas"

Local: Room 1.7, Edifício VII

Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: Os modelos de grafos têm vindo a assumir uma relevância crescente no estudo de redes complexas em áreas tão distintas como a análise de redes sociais, a bioinformática, o marketing e as finanças. Para compreender o comportamento de redes complexas é preciso identificar os grupos coesos que as integram e que, pela sua forte interconexão, podem influenciar de forma decisiva esse comportamento. As cliques em grafos são uma boa representação para grupos em que os elementos se relacionam todos dois a dois diretamente mas não captam as relações que que são estabelecidas através de intermediários. Para representar essas relações é necessário relaxar algumas das condições que definem uma clique.

Neste trabalho propomos uma nova relaxação do conceito de clique - o k-clube triangular - e um problema de otimização a ele associado - o problema do k-clube triangular máximo. Para este novo problema construímos modelos de Programação Linear Inteira em diferentes espaços de variáveis e analisamos as relações entre respetivas relações lineares comparando as suas projeções no espaço das variáveis de nodo. Para concluir, deduzimos famílias de desigualdades válidas para o poliedro do k-clube triangular e apresentamos resultados computacionais para redes scale-free e uniformes.

Em colaboração com Filipa D. Carvalho.