L'un des problèmes d'optimisation combinatoire les plus connus est le problème d'attribution. Voici un exemple: supposons qu'un groupe de nœuds de calcul doive effectuer un ensemble de tâches, et que pour chaque nœud de calcul et chaque tâche, l'attribution d'un nœud de calcul à la tâche entraîne un coût. Le problème consiste à attribuer chaque nœud de calcul au maximum à une tâche, sans que deux nœuds de calcul effectuent la même tâche, tout en minimisant le coût total.
Vous pouvez visualiser ce problème dans le graphique ci-dessous, qui comporte quatre nœuds de calcul et quatre tâches. Les arêtes représentent toutes les façons possibles d'affecter des nœuds de calcul à des tâches. Les étiquettes sur les arêtes correspondent aux coûts liés à l'affectation de nœuds de calcul aux tâches.
Une attribution correspond à un sous-ensemble d'arêtes, dans lequel chaque nœud de calcul a au maximum un bord sortant, et deux nœuds de calcul n'ont pas d'arêtes menant à la même tâche. Une attribution possible est illustrée ci-dessous.
Le coût total de l'attribution est de 70 + 55 + 95 + 45 = 265.
La section suivante explique comment résoudre un problème d'attribution à l'aide du résolveur MIP et du résolveur CP-SAT.
D’autres outils pour résoudre les problèmes des devoirs
OR-Tools fournit également d'autres outils pour résoudre les problèmes d'attribution, qui peuvent être plus rapides que les résolveurs MIP ou CP:
Toutefois, ces outils ne peuvent résoudre que des types de problèmes d'attribution simples. Ainsi, pour les solutions générales capables de gérer une grande variété de problèmes (et assez rapides pour la plupart des applications), nous recommandons les résolveurs MIP et CP-SAT.