Otimização combinatória

Otimização combinatória é um campo da matemática aplicada que se baseia no uso conjunto de técnicas de combinatória, programação matemática e teoria de desenvolvimento de algoritmos para resolver problemas de otimização formulados sobre estruturas discretas. Uma característica comum dos problemas de otimização combinatória é o fato de que o conjunto de soluções viáveis, embora seja finito, pode ser muito grande. Isso inviabiliza estratégias de força bruta, como testar todos os valores de solução possíveis, e torna necessário o desenvolvimento de métodos eficientes.

Problemas de otimização combinatória têm sido um tópico central para a evolução de algoritmos e da teoria de complexidade computacional. Pesquisadores têm apresentado muitas idéias criativas para o projeto de algoritmos eficientes, baseados em conceitos e resultados na área. A sub-área conhecida como combinatória poliédrica, por exemplo, apresenta técnicas desenvolvidas a partir de conceitos de programação linear, como o método primal-dual, e que têm se mostrado muito úteis no projeto e análise de uma variedade de algoritmos para problemas em outros domínios. Muitas das idéias inovadoras têm se baseado em um conjunto não muito grande de princípios comuns, como scaling, que são simultaneamente muito simples e muito poderosos.

Nem sempre, porém, é suficiente restringir a pesquisa de um problema ao estudo teórico de seus aspectos e ao desenvolvimento abstrato de algoritmos que o resolvem. Em diversos casos, existem fatores fundamentais que só podem ser resolvidos, ou mesmo descobertos, durante a implementação propriamente dita. Não é incomum que a obtenção de uma eficiência próxima àquela calculada na teoria, ou mesmo o próprio funcionamento de um algoritmo, dependa do uso de estruturas de dados sofisticadas e técnicas de programação que não são exatamente triviais.

Ademais, a complexidade de um algoritmo na teoria é muitas vezes um argumento questionável para classificá-lo na prática: não são incomuns algoritmos teoricamente eficientes mas lentos na prática, e algoritmos cuja análise de pior caso está longe de representar seu comportamento no caso médio. Diante dessa possibilidade, testes e experimentações são ferramentas poderosas e úteis, e que enfatizam ainda mais a importância da implementação.