Otimização Discreta e Grafos: Teoria, Algoritmos e Aplicações

Objetivos:

O foco central desta proposta é a investigação de problemas de Otimização Discreta e Grafos, com ênfase em seus aspectos teóricos, algorítmicos e aplicados.

Nossa proposta é desenvolver pesquisa de primeira linha nesse tema, trazendo contribuições de caráter prático e teórico. A área de Otimização Discreta se situa na fronteira entre a Ciência da Computação, a Matemática e as Engenharias, ocupando um lugar de grande destaque na pesquisa científica que vem sendo conduzida no mundo todo.

Dentre os vários problemas de otimização discreta que investigaremos incluem-se: projetos de redes de telecomunicações (redes de fibra ótica para conexões de banda larga), projetos de computadores e de chips VLSI, roteamento ou escalonamento de veículos, empacotamento de caixas em contêineres, corte de barras e placas, seqüenciamento de genes e DNA, mineração de dados, compressão de dados, etc.

Neste REDE focaremos o estudo de técnicas para a solução de problemas como os descritos acima, implementação eficiente dessas técnicas para a solução de problemas reais, e pesquisas de caráter mais teórico na área de grafos e combinatória.

Na área de grafos, serão pesquisados problemas sobre determinadas classes de grafos, bem como o desenvolvimento de algoritmos para a solução de problemas clássicos nessas classes e a análise da complexidade computacional dos problemas abordados. Pesquisas na área de grafos aleatórios também serão conduzidas. Esta área encontra-se na interseção das áreas de teoria dos grafos, combinatória e teoria das probabilidades. Consideramos o estudo de diversos problemas combinatórios, incluindo aspectos probabilísticos e assintóticos. Estes problemas têm um papel fundamental na investigação sobre grafos aleatórios e pseudo-aleatórios, assim como na análise assintótica de algoritmos e outras estruturas combinatórias.

Esta REDE é constituída pelos seguintes projetos temáticos, conduzidos por 6 grupo de pesquisa.

Grupo G1: Algoritmos exatos baseados em programação inteira e combinatória poliédrica

Grupo G2: Aplicação de técnicas de otimização combinatória a problemas reais de grande porte

Grupo G3: Metaheurísticas

Grupo G4: Algoritmos de aproximação

Grupo G5: Projeto e análise de algoritmos para problemas de corte e empacotamento

Grupo G6: Teoria dos Grafos: problemas estruturais, algorítmicos e assintóticos.

Os problemas que serão investigados são de grande interesse para o setor industrial, produtivo e público. Esperamos obter resultados de ponta que tragam benefícios para a área de pesquisa focada e também para a sociedade.

Além do foco no aspecto prático, entendemos que é importante dar ênfase aos estudos de caráter mais teórico, pois estes constituem o alicerce que dá sustentação ao desenvolvimento da área. Sem um forte embasamento teórico não ocorre um avanço científico e/ou tecnológico da área, e é esse avanço que em última instância beneficia a sociedade.

Objetivamos através desta REDE a construção de uma base sólida de conhecimentos e know-how na área de Otimização Discreta e Grafos no âmbito sul-americano. Objetivamos também fortalecer os programas de pós-graduação das instituções dos membros desta REDE através de mini-cursos ministrados por professores visitantes, teses co-orientadas e pesquisas conjuntas.

Fundamentalmente esperamos que, através de trabalhos conjuntos a serem desenvolvidos no âmbito desta REDE, possamos consolidar as cooperações existentes, estimular novas colaborações, aumentar o número de publicacões conjuntas e fomentar um maior número de doutorados, consolidando um grupo de sul-americanos com visibilidade e reconhecimento internacional na área em foco.