Assegnazione perfetta di 15000 dipendenti in 20 secondi. Evoluzione tecnologica (senza AI)

Dal Commesso Viaggiatore allo Smartphone in Tasca

Negli anni Settanta il problema del commesso viaggiatore era considerato il manifesto stesso dell’impossibile. Bastava aggiungere poche città e le combinazioni da esplorare esplodevano in maniera esponenziale. Gli algoritmi dell’epoca – backtracking, branch-and-bound primitivo, euristiche artigianali – richiedevano giorni di calcolo su macchine grandi quanto una stanza.

Il messaggio era chiaro: certi problemi combinatori sono teoricamente intrattabili. Cook (1971) lo aveva sancito con la NP-completezza, Karp (1972) aveva rafforzato la tesi: non c’è algoritmo polinomiale generale che ti salva. Fine della storia. O almeno così sembrava.

La rivoluzione

A partire dagli anni ’90 qualcosa è cambiato: sono arrivati i solver SAT e i constraint programming engine. Non più tentativi ciechi, ma propagazione di vincoli, clause learning, euristiche di ricerca parallele. Invece di esplorare tutto, si eliminano preventivamente milioni di possibilità impossibili. È come avere un navigatore che ti cancella le strade chiuse prima ancora di partire.

Google OR-Tools: l’algoritmo diventa pratico

Con OR-Tools (2011, Google) questo patrimonio di ricerca è diventato open source e industriale. Il solver CP-SAT oggi affronta varianti del TSP o problemi di assegnamento con vincoli incrociati (skill, distanze, triangolarizzazioni) che un tempo avrebbero richiesto un cluster di 100 supercomputer. Ora? Secondi su un portatile, minuti su un telefono.

Esempio concreto:

• Assegnare 15.000 dipendenti a 20 UO, rispettando triangolarizzazioni complesse. Con algoritmi greedy sequenziali: mesi di calcolo, risultati subottimali. Con OR-Tools: 18 secondi, soluzione matematica ottimale.

Dal mito dell’intrattabile alla pratica quotidiana

Non abbiamo sconfitto la teoria: NP-hard resta NP-hard. Ma la pratica è stata rivoluzionata. La combinatoria “impossibile” diventa gestibile perché:

• i vincoli reali restringono enormemente lo spazio di ricerca;
• i solver imparano dagli errori (clause learning);
• la ricerca è distribuita e parallela;
• la modellazione dichiarativa consente di cambiare vincoli senza riscrivere algoritmi.

Una metafora

È come passare da una bicicletta arrugginita che affrontava le Alpi negli anni ’70 a una Tesla in autopilot oggi: la montagna resta la stessa, ma l’esperienza è radicalmente diversa. Il commesso viaggiatore non solo parte: torna a casa per cena.

Conclusione

Il salto non è un dettaglio tecnico: è un breakthrough epocale. Dai tempi in cui servivano stanze di computer e calcoli interminabili, siamo arrivati a un presente in cui un cellulare risolve problemi che i matematici consideravano intrattabili. La teoria ci ricorda i limiti, la pratica ci mostra che – se ben modellati – quei limiti si aggirano ogni giorno.

E così, ciò che era il simbolo dell’impossibile è diventato… un’app da tasca.

Riferimenti

1. Google OR‑Tools (libreria open-source)
   Introduzione ufficiale e panoramica funzionale.
   Operations Research Stack Exchange+15Wikipedia+15Medium+15
2. Esempi pratici di assegnamento con vincoli (CP‑SAT)
   — “Assignment with Teams of Workers”: caso d’uso concreto con model CP‑SAT e vincoli di team.
   Google for Developers+15Google for Developers+15pganalyze+15
   — “Assignment with Task Sizes”: assegnamento con vincoli di capacità/“size” delle attività.
   Google for Developers
3. Approfondimento sulla logica e i parametri del CP‑SAT
   — Guida su parametri come max_time_in_seconds e logging per monitorare la ricerca.
   Google for Developers+13d-krupke.github.io+13Google Groups+13
   — Come interpretare i log del solver per controllo e ottimizzazione del modello.
   Google Groups+5d-krupke.github.io+5Google for Developers+5
4. OR‑Tools nella pratica industriale e ricerca recente
   — CP‑SAT continua a primeggiare nelle competizioni MiniZinc, confermando efficienza e robustezza.
   Stack Overflow+15Wikipedia+15arXiv+15
   — PyJobShop: integrazione di OR‑Tools CP‑SAT nei flussi di scheduling su larga scala.
   arXiv+2Stack Overflow+2
   — Risoluzione di varianti complesse del knapsack con conflitti tramite CP‑SAT.
   arXiv