Um dos problemas de otimização combinatória mais conhecidos é o problema de atribuição. Veja um exemplo: suponha que um grupo de workers precise executar um conjunto de tarefas e, para cada worker e tarefa, há um custo para atribuir o worker à tarefa. O problema é atribuir cada worker a no máximo uma tarefa, sem dois workers executando a mesma tarefa, minimizando o custo total.
É possível visualizar esse problema no gráfico abaixo, no qual há quatro workers e quatro tarefas. As bordas representam todas as maneiras possíveis de atribuir workers a tarefas. Os identificadores nas bordas são os custos de atribuir workers a tarefas.
Uma atribuição corresponde a um subconjunto das arestas, em que cada worker tem no máximo uma borda que sai da frente, e não há dois workers com bordas que levam à mesma tarefa. Uma possível atribuição é mostrada abaixo.
O custo total da atividade é de 70 + 55 + 95 + 45 = 265.
A próxima seção mostra como resolver um problema de atribuição usando o solucionador MIP e CP-SAT.
Outras ferramentas para resolver problemas na atribuição
O OR-Tools também fornece algumas outras ferramentas para resolver problemas de atribuição, que podem ser mais rápidas do que os solucionadores MIP ou CP:
No entanto, essas ferramentas só podem resolver tipos simples de problemas de atribuição. Portanto, para solucionadores gerais que podem lidar com uma grande variedade de problemas (e são rápidos o suficiente para a maioria dos aplicativos), recomendamos os solucionadores MIP e CP-SAT.