Diversas aplicações industriais necessitam extrair objetos menores de um matéria-prima de tamanho preestabelecido. Nesse contexto, almeja-se encontrar um leiaute de encaixe desses objetos diante de uma superfı́cie. Esse problema é conhecido na literatura como problema de corte e empacotamento que consiste em organizar os itens menores minimizando a área necessária para esse objetivo. Assim, esse projeto investiga uma fase posterior ao encaixe das peças, que é estabelecer uma ordem de corte para as arestas de todos os polı́gonos que são representações computacionais dos itens. Objetivando encontrar soluções para esse problema, apresenta-se uma abordagem fundamentada nos algoritmos genéticos de chaves aleatórias tendenciosas, inicialmente, e um conjunto de testes para análise do desempenho dessa concepção.

Este projeto trata do estudo e aplicação de ferramentas de aprendizado de máquina e otimização combinatória para duas classes de problemas: identificação de perfis em redes sociais e resolução de problemas de otimização combinatória com restrições sociais. Estas aplicações apresentam grandes desafios tecnológicos e têm em comum a necessidade de análises algorítmicas para busca de possíveis soluções. Por conta deste fator, a utilização de técnicas de programação linear inteira, meta-heurísticas e algoritmos de aprendizado de máquina mostram-se como ferramentas de modelagem promissoras. Aliada as modelagens, serão buscadas formas de extrair informações relevantes a partir dos dados coletados em redes sociais. Estes dados serão processados utilizando algoritmos de aprendizado de máquina, inicialmente para classificar perfis em redes sociais e posteriormente como entrada para os problemas de otimização combinatória com restrições sociais.

Há décadas, a tecnologia tem contribuído com soluções disruptivas que otimizam processos nos mais diversos setores da economia. Não sendo diferente, no mundo rural, que já vivencia a chamada "Agricultura 4.0", onde a aplicação de técnicas computacionais se faz cada dia mais presente. Esse fenômeno vai além da simples mecanização do campo, uso de sensores e gps. As operações e decisões passam a ser orientadas com base em dados retirados do clima, da terra, da lavoura etc. Em consonância com essa visão, este projeto busca criar ferramentas inteligentes para auxílio na tomada de decisão em relação a colheita e uso de recursos hídricos, conciliando para tal, técnicas de visão computacional, uso de Big Data Analysis e otimização combinatória para analisar dados e imagens de lavouras de frutos cítricos com intuito de melhorar a captação de aćido ascórbico e reduzir o uso de irrigação em fazendas situadas no interior do estado do Ceará.

Os problemas de otimização combinatória podem ser de minimização ou de maximização de uma função, aplicada a um conjunto finito, que em geral é enumerável, onde se deseja obter a melhor solução possível. Existe alguns problemas de otimização que são classificados como problemas NP-Difíceis, como por exemplo o problema da mochila. Alguns deles, problema do corte máximo, problema da diversidade máxima, problema do caixeiro viajante etc, podem ser modelados com grafos. Para essa classe de problemas os algoritmos heurísticos são na maioria das vezes preferidos, em relação ao exatos, para encontrar soluções quase ótimas em um período de tempo aceitável. Em contrapartida aos algoritmos exatos, e as meta-heurísticas tradicionais e evolucionárias, o aprendizado de máquina explora o estudo e construção de algoritmos que podem aprender de seus erros e fazer previsões sobre dados. Esse projeto pretende investigar o uso de algumas abordagens do aprendizado de máquina na busca de soluções em problemas de otimização em grafos.

Costuma-se chamar de programação quadrática a subárea que engloba problemas de otimização consistindo na maximização/minimização de uma função quadrática sujeita a restrições expressas por igualdades/desigualdades lineares. Particularmente, quando as variáveis do problema estão restritas a valores 0 − 1, encontramo-nos no escopo da programação quadrática binária. Dentre as técnicas de linearização usadas em problemas quadráticos 0 − 1, a t-linearização é uma abordagem recente e ainda pouco estudada tendo sido aplicada nos seguintes problemas: Problema Quadrático da Mochila; Problema do Corte Máximo; e Problema da Diversidade Máxima. Esse projeto pretende investigar a aplicabilidade da t-linearização em outros problemas quadráticos 0-1.

Problemas de coloração podem ser formulados como segue: Dado um grafo, desejamos colorir os vértices satisfazendo uma restrição pré-definida, comumente que vértices adjacentes devem ter cores distintas. Diversos problemas reais podem ser modelados como problemas de coloração em grafos, por exemplo, alocação de frequências em redes de telefonia e alocação de tarefas em processadores. Neste contexto, algoritmos eficientes e, mais importante, exatos para o problema representam um ganho considerável de recursos. Neste projeto analisamos problemas de coloração que possuem restrições particulares e desenvolvemos algoritmos exatos para estes variações do problema de coloração. Usualmente estes algoritmos usam técnicas de programação matemática.

Relaxação lagrangeana é uma técnica de relaxação usada em problemas de otimização para se obter um limitante inferior ou superior a depender do sentido da função objetivo (maximização ou minimização). Em problemas de otimização combinatória, onde obter limitantes é desafiador esta técnica ganha em importância, este é o caso dos problemas de coloração. Em problemas de coloração, desejamos colorir os vértices de um grafo dado como entrada satisfazendo algumas restrições pré-definidas. Neste projetos estudamos maneiras de obter limitantes para diversos problemas de coloração na literatura utilizando relaxação lagrangeana.

Dado um grafo podemos imaginar que este possui um conjunto de vértices infectados com um vírus que se propaga pelo grafo seguindo uma regra bem-definida. Este tipo de problema é chamado de problema de infecção em grafos e está relacionado a diversos parâmetros de grafos em teoria dos grafos, como convexidade por exemplo, além de poder ser utilizado para modelar diversos problemas reais, como alocação de transmissores por exemplo. Neste projeto nós nos dedicamos a formalizar a propor algoritmos exatos e heurísticas para diversos problemas de infecção em grafos.