Otimização Combinatória

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.

Descrição informal de alguns destes problemas:

Podemos também considerar adicionar restrições de segurança contra falhas. Por exemplo, a rede poderia ser construída de tal maneira que mesmo que uma conexão ligando dois computadores fique temporariamente fora do ar, a rede projetada deve permitir uma rota alternativa que ligue todos os computadores principais.

Exemplo de rede conectando cidades. As cidades importantes (em vermelho) continuam ligadas mesmo que uma conexão falhe.

Cidades ligadas por uma rede com caracteristicas retilineares

Em circuitos VLSI, há restrições na forma das ligações, que muitas vezes devem ser horizontais ou verticais. Os pontos em azul, da figura acima devem estar ligados por uma rede.

Problema do Caminho Mínimo
Um dos problemas mais estudados em Otimização Combinatória, é o problema de ligar dois pontos de custo mínimo. Neste caso, temos um mapa de ligações entre pontos (não necessariamente para cada par) e cada ligação tem um custo para ser percorrido. Além disso, temos um ponto inicial e um ponto final. O caminho de custo mínimo é a seqüência de ligações que se deve seguir do ponto inicial até o ponto final, cujo custo total é mínimo. Apesar de bastante estudado, este é ainda um problema bastante interessante, principalmente quando se é exigido que tenhamos soluções rápidas para mapas contendo dezenas de milhões de pontos e ligações.

Problema do caminho mínimo usado em segmentacão de imagens

Exemplo do Problema do Caminho Mínimo aplicado à segmentação de imagens.

Problema do Caixeiro Viajante
Uma fábrica de componentes eletrônicos precisa soldar milhares de placas de circuitos impressos. Para agilizar, todas as placas de mesmo tipo são soldadas uma após a outra, em pontos previamente especificados. O objetivo é saber qual o trajeto das posições que a máquina de solda deve percorrer para que gaste o menor tempo possível em cada placa. Note que qualquer ganho de tempo neste trajeto pode ser crucial para se soldar as milhares de placas em pouco tempo.

Agora, suponha que você quer conhecer algumas cidades do Estado de Sao Paulo e a partir de uma cidade inicial, percorrer outras cidades e voltar à cidade de inicial, gastando o menor tempo possível.

Considere que você tem um depósito (matriz) de onde saem caminhões carregados de certos produtos e devem passar por algumas cidades. Porém, em cada cidade o caminhão deve entregar certos produtos e há uma capacidade máxima que o caminhão pode carregar em cada viagem. O objetivo é minimizar o gasto total (digamos em kilometros rodados) para entregar todos os produtos e respeitando a capacidade do caminhão. Exemplo de rotas:

Exemplo: Classificação dos pixels de uma imagem. A esquerda temos uma imagem com 50% de degradação e a direita, a imagem com seus pixels classificados em preto ou branco.

Problemas de Corte e Empacotamento
Considere agora que você está construindo um prédio. As janelas e divisórias de vidro do prédio são necessárias em quantidade e tamanhos diferentes. A construtora faz o pedido de compra a uma vidraçaria, especificando as dimensões e quantidades de cada item. A vidraçaria deve cortar estes pedaços a partir de placas de vidro de tamanhos fixos, que são fornecidas pelo fabricante de vidro. Para minimizar os custos, o objetivo da vidraçaria é usar o menor número destas placas.

Note que um problema relacionado, mas agora tridimensional, é o problema de empacotar objetos dentro de containeres, de maneira a maximizar a carga no container, ou minimizar a quantidade de conteineres usados para transportar determinado conjunto de objetos.

Atribuições de Freqüências em Telefonia de Celular
Considere agora uma empresa que tem várias torres (antenas) que cobrem uma determinada região por onde trafegam usuários de telefone celular. Quando duas antenas muito próximas recebem as mesmas freqüencias, a região que sofre a cobertura destas antenas apresenta muita interferência. O objetivo é atribuir as freqüências (de quantidade limitada) para as antenas de maneira a minimizar a interferência total da atribuição.

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

Descrição informal de alguns destes problemas:

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