Uno dei problemi di ottimizzazione combinatoria più noti è il problema di assegnazione. Ecco un esempio: supponiamo che un gruppo di lavoratori debba eseguire una serie di attività e che per ogni worker e attività sia previsto un costo per l'assegnazione del worker all'attività. Il problema è assegnare ogni worker al massimo a un'attività, senza che due worker eseguano la stessa attività, riducendo al minimo il costo totale.
Puoi visualizzare questo problema dal grafico qui sotto, in cui ci sono quattro worker e quattro attività. I bordi rappresentano tutti i modi possibili per assegnare worker alle attività. Le etichette ai bordi rappresentano i costi associati all'assegnazione dei lavoratori alle attività.
Un'assegnazione corrisponde a un sottoinsieme di perimetri, in cui ciascun worker ha al massimo un bordo che conduce all'esterno e nessun worker ha un bordo che conduce alla stessa attività. Di seguito è riportata una possibile assegnazione.
Il costo totale dell'assegnazione è 70 + 55 + 95 + 45 = 265.
La sezione successiva mostra come risolvere un problema di assegnazione, utilizzando sia il risolutore MIP sia quello CP-SAT.
Altri strumenti per risolvere problemi relativi ai compiti
OR-Tools fornisce anche un paio di altri strumenti per risolvere problemi di assegnazione, che possono essere più veloci dei risolutori MIP o CP:
Tuttavia, questi strumenti possono risolvere solo tipi semplici di problemi relativi ai compiti. Per i risolutori generici in grado di gestire un'ampia varietà di problemi (e abbastanza veloci per la maggior parte delle applicazioni), consigliamo i risolutori MIP e CP-SAT.