otimização combinatória

Otimização Combinatória
Prof. Flávio Keidi Miyazawa

Problemas de otimização, na sua forma geral, têm como objetivo maximizar ou minimizar uma função definida sobre um certo domínio. A teoria clássica de otimização trata do caso em que o domínio é infinito. Já no caso dos chamados problemas de otimização combinatória, o domínio é tipicamente finito; além disso, em geral é fácil listar os seus elementos e também testar se um dado elemento pertence a esse domínio. Ainda assim, a idéia ingênua de testar todos os elementos deste domínio na busca pelo melhor mostra-se inviável na prática, mesmo para instâncias de tamanho moderado.
Como exemplos clássicos de problemas de otimização combinatória podemos citar o problema do caixeiro viajante, o problema da mochila, o problema da cobertura mínima por conjuntos, o problema da floresta de Steiner e o problema da satisfatibilidade máxima. Todos surgem naturalmente em aplicações práticas, tais como o projeto de redes de telecomunicação e de circuitos VLSI, o empacotamento de objetos em containers, a localização de centros distribuidores, o escalonamento e roteamento de veículos, etc. Outras áreas de aplicação incluem a estatística (análise de dados), a economia (matrizes de entrada/saída), a física (estados de energia mínima), a biologia molecular (alinhamento de DNA e proteínas, inferência de padrões), etc.
Estratégias que tem tido sucesso no tratar destes problemas envolvem métodos em programação inteira, algoritmos probabilísticos e algoritmos de aproximação.
Descrição informal de alguns destes problemas:

Projeto de Redes com Restrições de Conectividade
Projeto do Caminho Mínimo
Problema do Caixeiro Viajante
Problema do Roteamento de Veículos
Corte de Placas
Escalonamento de Tarefas
Problemas de Classificação e Particionamento
Problemas de Corte e Empacotamento
Atribuições de Freqüências em Telefonia de Celular Projeto de Redes com Restrições de Conectividade
Suponha que você está projetando uma rede