Otimização combinatória
Keywords: Otimização combinatória, Investigação Operacional, Lista de algoritmos, Redes neurais, Teoria dos grafos, Colônia de formigas, Busca tabú, Algoritmos genéticos, GRASP, Simulated annealing
A Otimização Combinatória é um ramo da ciência da computação que estuda problemas de otimização em conjuntos.
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 Ótimo Global - a essas soluções chamamos de Ótimo Local.
Existem muitas classificações possível 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ística), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade (poderia ser criado artigo sobre isso) 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ções
Para mais informações, ver Lista de algoritmos.
Algumas das técnicas de obtenção de soluções aproximadas:
Algoritmos genéticos (Genetic Algorithms, em inglês)
Busca tabú (Taboo Search, em inglês)
Colônia de formigas (Ant Colony, em inglês)
Greedy Randomized Adaptive Search Procedures (GRASP, sigla)
Redes neurais (Neural Networks, em inglês)
Simulated annealing (Anelagem Simulada, em português)
Dentre as classificações possíveis, seguem abaixo algumas:
1) Quanto à relação entre as variáveis de decisão na função objetivo e nas restrições:
A) Programação Linear
B) Programação Não-Linear
2) Quanto ao valor que podem assumir as variáveis:
A) Programação Real (nome não-utilizado, apenas posto aqui para diferenciação)
B) Programação Inteira
C) Programação 0-1 (variáveis inteiras, com apenas dois valores possíveis)
D) Programação Mista (algumas variáveis reais e outras inteiras)
3) Quanto à natureza da função objetivo:
A) Função Convexa - Ótimo Local é Global (mais simples)
B) Função Côncava - Ótimo Local não necessariamente Gloal (mais complicado de resolver)