OR-Tools è il software open source per l'ottimizzazione combinata, che cerca di trovare la soluzione migliore a un problema tra una vastissima serie di possibili soluzioni. Di seguito sono riportati alcuni esempi di problemi risolti con OR-Tools:
- Routing dei veicoli: trova percorsi ottimali per le flotte di veicoli che ritirano e consegnano i pacchi a causa di limitazioni (ad esempio "questo camion non può contenere più di 15.000 kg" o "tutte le consegne devono essere effettuate entro due ore".
- Pianificazione: individua la pianificazione ottimale per un insieme complesso di attività, alcune delle quali devono essere eseguite prima di altre, su un set fisso di macchine o altre risorse.
- Imballaggio bin: raccogli il maggior numero possibile di oggetti di varie dimensioni in un numero fisso di bin con capacità massime.
Nella maggior parte dei casi, problemi come questi hanno una vasta gamma di possibili soluzioni, troppe per fare in modo che un computer le cerchi tutte. Per ovviare a questo problema, OR-Tools utilizza algoritmi all'avanguardia per restringere il set di ricerca, in modo da trovare una soluzione ottimale (o quasi).
OR-Tools include risolutori per:
- Programmazione dei vincoli
- Un insieme di tecniche per trovare soluzioni applicabili a un problema espresso come limiti (ad es. una stanza non può essere utilizzata per due eventi contemporaneamente o la distanza tra i colpi deve essere inferiore alla lunghezza del tubo o non è possibile registrare più di cinque programmi TV contemporaneamente).
- Programmazione con numeri interi e misti
- Lo strumento di ottimizzazione lineare Glop trova il valore ottimale di una funzione dell'obiettivo lineare, dato un insieme di disuguaglianze lineari come vincoli (ad esempio, assegnando le persone ai lavori o trovando la migliore allocazione di un insieme di risorse, riducendo al minimo i costi). Glop e il software di programmazione a numeri interi SCIP sono disponibili anche tramite il Servizio di ottimizzazione di Google Apps Script.
- Routing del veicolo
- Una raccolta specializzata per identificare i percorsi migliori dei veicoli in base ai vincoli.
- Algoritmi di grafica
- Codice per individuare i percorsi più brevi nei grafici, nei flussi minimi, nei flussi massimi e nelle assegnazioni di somma lineare.
Nella sezione successiva inizierai a utilizzare rapidamente OR-Tools.