Otimização Combinatória

Otimização é o processo de buscar a melhor solução dentre um conjunto de soluções disponíveis para um problema.

Possui três elementos: as varáveis de decisão (parâmetros para solução do problema), função objetivo (função a ser maximizada e minimizada) e as restrições (define o espaço de soluções desejadas).

Em um sistema de produção as variáveis de decisão podem representar as quantidades produzidas de determinados objetivos; a função objetivo pode ser o interesse relacionado aos custos na produção,(maximizar os ganhos ou minimizar os custos); e as restrições podem ser as limitações operacionais do processo de produção, como quantidade de objetos a serem utilizados.

Otimização Combinatória tenta determinar valores a variáveis de decisão, de modo que uma função desenvolvida utilizando essas variáveis seja otimizada na presença de um conjunto de restrições e pesos associados as variáveis.

Um problema que pode ser modelado como um grafo, pode ser dito como um Problema de Otimização Combinatória.

Podem ser de cinco classes:

• Problemas de conexão: Árvores, Caminho e Emparelhamento. Ex: Árvore Geradora Miníma, N-Rainhas, Caminho Mínimo, e Emparelhamento Bipartido, etc.
• Problemas de Fluxo em Redes: Processo de otimização da distribuição de itens originados em um vértice e consumidos em outros vértices. Ex: Transporte, Alocação, Problema do Transbordo, etc.
• Problema do Caixeiro Viajante: Encontrar o menor custo que se inicie e termine em um vértice passando pelos demais, sem repetição.
• Problemas de Roteamento: Atender demandas localizadas nas arestas ou nos vértices de uma rede. Problema do Carteiro Chines, Roteamento de Veículos e Escala de Tripulação.
• Problemas de Cobertura e Particionamento: É quando se procura o menor conjunto de vértices/arestas tal que toda(o) aresta/vértice do grafo incida em um(a) destes(as) vértices/arestas. Ex: Localização de Facilidades, Localização de Antenas e Radares.

Um conjunto de soluções viáveis, nesse tipo de problema, é muito grande, embora finito. Impossibilitando o uso de busca bruta, que testa todos os valores de soluções possíveis. Para algumas classes é possível utilizar métodos exatos de resolução, a Programação Matemática. Para outras há a necessidade de métodos não-exatos, tais como Heurísticas (Busca Gulosa, Busca em Profundidade, Algoritmo de Dijkstra, Algoritmo de Kruskal, etc) ou Metaheurísticas (Busca Tabu, Algoritmos Genéticos ou Colônia de Formigas).

Fonte: Pires, M. G. Abordagem Neuro-Genética para Mapeamento de Problemas de Conexão em Otimização Combinatória. Tese (Doutorado) - Escola de Engenharia de São Carlos, Universidade de São Paulo. 2009.