Otimização Combinatória

A Otimização Combinatória é uma sub-área da Pesquisa Operacional que lida com problemas de otimização em conjuntos de soluções finitos, como, por exemplo, problemas de decisão de sequência, programação, agendamento, itinerários, entre outros.

Problemas Clássicos

Problema da Mochila

Imagine que você seja contemplado com um cruzeiro marítimo com tudo pago e direito a um acompanhante. Nesse cruzeiro só tem gente da alta sociedade como políticos, jogadores de futebol, médicos, cientistas, engenheiros, entre outros. Em alto mar o navio começa a afundar. Só existe um barco salva-vidas, que, no entanto, tem um limite de peso. Portanto não podemos colocar todas as pessoas no barco.

Supondo que cada pessoa tem um peso e um grau de importância. E agora? Quem deverá ser salvo? Esse problema é conhecido como o Problema da Mochila. Nesse caso a mochila é o barco salva-vidas.

Para n pessoas há 2ⁿ soluções possíveis. Exemplo: Para 50 pessoas há 10¹⁵ soluções para serem testadas. Se tivéssemos um computador que realizasse uma avaliação em 10^-8 segundos, ele gastaria cerca de 130 dias para encontrar a melhor solução enumerando todas as possíveis soluções. Conclusão: O barco afundaria antes mesmo que fosse tomada a decisão dos escolhidos.

Um excursionista planeja fazer uma viagem acampando. Há 5 itens que ele deseja levar consigo, mas estes, juntos, excedem o limite de 60 quilos que ele supõe ser capaz de carregar. Para ajudar a si próprio no processo de seleção, ele atribui valores, por ordem crescente de importância a cada um dos itens conforme a tabela a seguir:

Problema da Partição de Números

O problema de partição de números consiste em: dado um conjunto de N números, o objetivo é subdividi-lo em dois subconjuntos (chamados de partições) de tal forma que, a diferença entre os valores das somas dos números dessas duas partições seja a menor possível. Por exemplo, considere o seguinte conjunto com quatro números (23, 20, 56, 48). As partições (20,56) e (23,48) consistem no particionamento ótimo para este conjunto e, seu valor é 5. Apesar da simplicidade do enunciado, este é um problema de otimização combinatória que pertence a classe NP-difícil. Observe que, para um conjunto com n números têm-se 2ⁿ possíveis maneiras de subdividi-lo em duas partições.

Problema do Caixeiro Viajante (PCV)

Dado um conjunto de cidades e uma matriz de distâncias entre elas.

PCV consiste em encontrar uma rota tal que esta:

parta de uma cidade origem.
passe por todas as demais cidades uma única vez.
retorne à cidade origem ao final do percurso.
percorra a menor distância possível.

Considerando PCV simétrico, para n cidades há (n-1)!/2 rotas possíveis. Para n = 20 cidades, há 10¹⁶ rotas possíveis. Um computador que avalia uma rota em 10⁻⁸ segundos gastaria cerca de 19 anos para encontrar a melhor solução por enumeração completa.

Download de instâncias do PCV: Clique aqui.

Métodos de Resolução

Programação Matemática

Características Básicas:

Fundamentação: na matemática.
Vantagem: garantem a solução ótima (menor custo).
Desvantagens:
- Modelagem mais complexa.
- Podem gastar um tempo proibitivo para gerar a solução ótima.
- Nem sempre conseguem produzir uma (boa) solução viável rapidamente.

Exemplos: Branch-and-Bound, Planos de Corte, Enumeração Implícita.

Métodos Heurísticos

Características Básicas:

Fundamentação: na Inteligência Artificial (IA).
Vantagens:
- De fácil implementação.
- Produzem boas soluções rapidamente.
Desvantagem: Não garantem a otimalidade da solução obtida.

Exemplos: GRASP, ILS, Simulated Annealing, Algoritmos Genéticos.