A '''OptimizaçãoOtimizaçã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 optimizaçãootimizaçã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 ''óptimoó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 ''óptimoótimo local''.
Há muitas classificações possíveis para o problema de optimizaçãootimização, e algumas delas apresentarão métodos exactosexatos e eficientes de resolução. Outras levarão à necessidade de métodos não-exactosexatos ([[heurística]]s), uma vez que sua formulação e/ou resolução exatas levariam a uma [[Complexidade computacional|complexidade intratável]].
Como técnicas de soluções exatas - em especial com algoritmo polinomial para alguns problemas - temos, por exemplo:
Linha 34:
3) Quanto à natureza da função objetivo:
*Função convexa - ÓptimoÓtimo local é global (mais simples)
*Função côncava - ÓptimoÓtimo local não necessariamente Global (mais complicado de resolver)