Otimização Combinatória

Problemas de otimização combinatória são aqueles em que há um número finito de soluções possíveis e se busca uma solução ótima, ou seja, aquela que maximiza os ganhos ou minimiza os custos.

Muitos problemas nas áreas de produção, logística e transportes são problemas de otimização combinatória. Incluem-se nessa categoria, por exemplo, problemas de programação da produção, corte e empacotamento de materiais, alocação de recursos e roteirização de veículos.

Os problemas de otimização combinatória se caracterizam pelo crecimento exponencial no número de soluções possíveis, de forma que é praticamente impossível obter boas soluções para problemas reais de larga escala por tentativa e erro. No entanto, é possível obter boas soluções ou até soluções ótimas por meio de algoritmos que explorem inteligentemente a estrutura matemática do problema. Para isso utilizam-se algoritmos de programação matemática, programação dinâmica e heurísticas.

As principais tecnologias utilizadas para a implementação dos algoritmos são a linguagen Python e solvers como o IBM CPLEX, Gurobi e COIN-OR CBC.