Otimização combinatória

A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos.

Em um problema de otimização temos uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. O problema pode ser de minimização ou de maximização da função objetivo. A resposta para o problema, ou seja, o ótimo global, será o menor (ou maior) valor possível para a função objetivo para o qual o valor atribuído às variáveis não viole nenhuma restrição. Em alguns casos, chegamos a valores cuja alteração discreta não conduz a resultados melhores, mas que não são também o óptimo global - a essas soluções chamamos de ótimo local.

Há muitas classificações possíveis para o problema de otimização, e algumas delas apresentarão métodos exatos e eficientes de resolução. Outras levarão à necessidade de métodos não-exatos (heurísticas), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade intratável.

Como técnicas de soluções exatas - em especial com algoritmo polinomial para alguns problemas - temos, por exemplo:

• Algoritmos de grafos (ver Teoria dos grafos)
• Algoritmos gulosos
• Algoritmo simplex
• Branch e bound
• Programação dinâmica
• Relaxação lagrangeana

Algumas das técnicas de obtenção de soluções aproximadas:

• Algoritmos genéticos
• Busca tabu
• Algoritmo da colônia de formigas
• Greedy Randomized Adaptive Search Procedures (GRASP)
• Redes neurais
• Simulated annealing (arrefecimento simulado)

Entre as classificações possíveis, encontram-se:

1) Quanto à relação entre as variáveis de decisão na função objetivo e nas restrições:

• Programação linear
• Programação não-linear

2) Quanto ao valor que podem assumir as variáveis:

• Programação real (nome não-utilizado, apenas posto aqui para diferenciação)
• Programação inteira
• Programação 0-1 (variáveis inteiras, com apenas dois valores possíveis)
• Programação mista (algumas variáveis reais e outras inteiras)

3) Quanto à natureza da função objetivo:

• Função convexa - Ótimo local é global (mais simples)
• Função côncava - Ótimo local não necessariamente Global (mais complicado de resolver)

Alguns Problemas de Otimização Combinatória

• Problema de Roteamento de Veículos

Ver também

• Investigação Operacional
• Lista de algoritmos