Esta linha de pesquisa se desdobra na (i) modelagem computacional de problemas de otimização fundamentais ou originados em aplicações nas áreas de telecomunicações, transportes, esportes, manufatura, biologia e medicina, assim como a busca de algoritmos eficientes para a resolução de tais problemas e na (ii) fundamentação e análise de Algoritmos, enviesando a estudos de complexidade por métodos exatos, aproximativos e parametrizados e também por construção e transformação de modelos para raciocínio e verificação de propriedades. Encontra-se articulada em torno de três linhas de pesquisa que se complementam: Otimização Combinatória, Algoritmos em Grafos e Teoria da Computação.

Nessa linha são estudados e desenvolvidos modelos e métodos computacionais para tratar problemas originados da Biologia Molecular. Alguns problemas clássicos na área são a construção de árvores filogenéticas, o sequenciamento de DNA e a determinação da estrutura espacial de moléculas. Tais problemas envolvem, em geral, conjuntos muito grandes de dados que devem ser armazenados, manipulados e interpretados.

Nesta linha são estudados e desenvolvidos algoritmos e procedimentos envolvendo a Computação Quântica. Também são analisados os impactos da Computação Quântica para áreas como segurança da informação.

Essa linha trata da formulação e da solução de problemas que envolvem a determinação da melhor alocação de recursos para um conjunto de atividades, de modo a otimizar um ou mais objetivos pré-estabelecidos (tais como minimizar custos ou riscos, ou maximizar lucros ou confiabilidade) sob determinadas restrições. Desenvolvem-se métodos exatos e métodos aproximados para a solução de tais problemas. Em termos de aplicações de interesse, podem ser citados o projeto e a operação de transportes e telecomunicações; o planejamento da operação e da expansão de sistemas de geração de energia; a organização de sistemas de manufatura flexível; a localização de facilidades e a alocação ótima de recursos; o sequenciamento de atividades; a exploração ótima de campos petrolíferos e a gestão de eventos esportivos, entre muitas outras.

Metaheurísticas são procedimentos genéricos que coordenam heurísticas simples, de modo a encontrar ótimos locais para a solução de problemas combinatórios em tempo computacional reduzido. Diferentes estratégias de exploração do espaço de soluções permitem escapar de convergência prematura, levando aos métodos conhecidos como busca tabu, simulated annealing, greedy randomized adaptive procedures (GRASP), algoritmos genéticos, colônias de formigas, scatter search, busca em vizinhança variável (VNS) e reconexão por caminhos, entre outros. São desenvolvidas pesquisas voltadas ao desenvolvimento de algoritmos eficientes e de técnicas para comparação de algoritmos, assim como estudos de paralelização de heurísticas em ambientes de clusters e grids, assim como sua aplicação em problemas de redes de telecomunicações, no desenvolvimento de sistemas inteligentes para roteamento e transporte público, e na gestão de eventos esportivos.

Grafos são estruturas discretas que modelam matemática e computacionalmente inúmeros problemas reais de natureza combinatória. Os nós de um grafo representam os objetos individuais do universo em estudo, e as arestas representam as relações existentes entre tais objetos. Muitas propriedades estudadas na Teoria de Grafos auxiliam diretamente na resolução dos problemas modelados, tornando mais eficientes os algoritmos empregados. Entre os temas de interesse desta linha de pesquisa, pode-se mencionar o estudo de classes de grafos e propriedades estruturais, os problemas de particionamento e clusterização, e a complexidade de algoritmos.