il numero massimo di BoolVar prima di or-tools non è più fattibile da usare
Il problema di pianificazione infermieristica standard utilizzato come esempio per gli strumenti di sala operatoria (vedere ad esempio https://developers.google.com/optimization/scheduling/employee_scheduling) tenta di assegnare valori booleani a variabili booleane nella seguente riga di codice:
shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))
Per questo problema con i giocattoli, OR-Tools funziona bene, ma vengono create solo 105 variabili booleane (5 infermieri, 7 giorni, 3 turni $\Rightarrow 3\times 5\times7=105$ valori booleani per assegnare se un dato infermiere lavora in un dato turno).
Sto esplorando l'uso degli strumenti OR per risolvere un problema di pianificazione del mondo reale più realistico. Per il problema del mondo reale che sto affrontando, i turni vengono assegnati in incrementi di 15 minuti e ci sono più lavoratori e più ruoli coinvolti. Alla fine, mi ritrovo con 11.064 booleani da assegnare.
Sono troppe per aspettarsi che gli OR-Tools funzionino in modo realistico? Trovo che produca rapidamente un programma (non molto buono) ma poi, anche se lo lascio funzionare per un'ora, non migliora affatto rispetto al programma iniziale che è venuto fuori nei primi secondi.
È questo un comportamento tipico per gli strumenti OR? qualche idea?
Risposte
Non ci sono buone risposte a questa domanda. Dipende dal modello, dalla complessità del problema. La mia reazione istintiva è che OR-Tools risolve regolarmente all'ottimalità problemi più grandi, ma alcuni problemi molto più piccoli possono essere impossibili da provare, o anche da trovare una soluzione fattibile.
OR-Tools è un buon risolutore di CP (ha vinto tutte e 4 le medaglie d'oro delle ultime 2 sfide minizinc). È anche un discreto risolutore MIP (ha chiuso 5 istanze MIPLIB 2017 aperte e ha migliorato i limiti su alcune altre).
Suggerirei o ripeterei i suggerimenti di cui sopra:
- confrontalo con un risolutore MIP commerciale (Gurobi, Cplex, Xpress) e prova la fortuna.
- confronta con CPLEX CP-Optimizer. Non mi aspetto che sia migliore dopo le discussioni che ho avuto con i ricercatori accademici che hanno fatto il confronto, ma questo potrebbe essere un problema quando CPO si comporta in modo eccellente.
- invia il tuo modello alla mailing list degli utenti di or-tools e chiedi aiuto o commenti, in particolare sui parametri di ricerca.