Continuiamo con la serie delle Letture Matematiche. Dopo l’articolo sul Traveling Salesman Problem a cura di Marco Menale, vi proponiamo una recensione di “In Pursuit of the Traveling Salesman”, un libro interamente incentrato proprio sul problema del commesso viaggiatore, a cura di Alice Raffaele.

Il problema del Traveling Salesman Problem (TSP) è così formulato: “Date n città di cui si conoscono tutte le relative distanze, partendo da una di queste, quanto è lungo il percorso minimo per visitarle tutte, una e una sola volta, facendo ritorno al punto di partenza?”

In apparenza non sembra troppo difficile. E invece è un problema su cui matematici e informatici, soprattutto coloro che si occupano di Ricerca Operativa, stanno lavorando da decenni. È il caso per esempio di William J. Cook, professore di Matematica Applicata e Statistica alla Johns Hopkins University e di Ottimizzazione Combinatoria alla University of Waterloo. Cook è considerato una delle persone più esperte al mondo sul TSP. È anche uno degli autori, insieme a David Applegate, Robert E. Gizby e Vašek Chvátal, del Concorde TSP Solver, un software sviluppato appositamente per risolvere istanze del TSP.

William J. Cook (fonte: Wikipedia)

Quali sono stati i passaggi fondamentali negli anni di ricerca su questo problema? E in quali contesti può essere applicato? Cook ha deciso di raccogliere tutto e molto altro in merito al TSP in un saggio divulgativo, pubblicato dalla Princeton University Press nel 2012, intitolato “In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation”.

Lo scopo principale del libro, come scritto da Cook nella prefazione, è quello di interessare il lettore, incoraggiandolo a seguire nuove strade per trovare una soluzione a questo avvincente problema, per un qualsiasi n. Il libro è rivolto sia a coloro che sono già familiari con il TSP sia a coloro che non ne hanno mai sentito parlare (o, meglio, che pensano di non averne mai sentito parlare!).

“In Pursuit of the Traveling Salesman” può essere definito completo, in quanto tratta il TSP da più punti di vista. Approfondisce infatti diverse facce di questo poliedrico problema, alcune più discorsive e altre un po’ più tecniche. Se il lettore è più interessato alla storia del TSP, troverà entusiasmanti i primi capitoli in cui Cook ripercorre le origini del problema, dalle prime formulazioni dell’Ottocento, passando per l’avvento e l’applicazione della Programmazione Lineare al TSP con George B. Dantzig, Delbert R. Fulkerson e Selmer M. Johnson (che nel 1954 riuscirono a risolvere un’istanza del TSP su 49 città), fino ad arrivare a oggi, quando la più grande istanza risolta esattamente (proprio dal Concorde nel 2006) ha n = 85.900 punti.

L’istanza delle 49 città degli Stati Uniti (fonte: https://www.math.uwaterloo.ca/tsp/ )

Nel capitolo “The Salesman in Action”, Cook presenta una serie di applicazioni pratiche del TSP, dai classici problemi di routing (che devono essere risolti, per esempio, dai software nei navigatori stradali) alle mappe del genoma, dall’astronomia alla cristallografia, ma anche ai videogiochi e al design dei microprocessori, e molte altre.

Come si può ottenere una soluzione, anche soltanto ammissibile? Non esistono solo metodi di forza bruta, che provano tutti i possibili ordinamenti delle città per determinare una soluzione ottima, come hanno assunto erroneamente alcune testate giornalistiche negli ultimi decenni e come riportato da Cook nella IFORS Distinguished Lecture che ha tenuto durante EURO 2019:

Nella parte centrale del libro, Cook parte descrivendo semplici euristiche costruttive come quella di Nearest Neighbor (in italiano, il Metodo del Vicino più Prossimo: partendo da una città, si sceglie come successiva quella più vicina, e così via fino a quando non si è completato il ciclo). Riporta anche algoritmi come il famoso di 3/2-approssimato di Christofides sviluppato nel 1976, ed euristiche più complesse, come Simulated Annealing e algoritmi genetici. Cook dedica poi ampio spazio alla Programmazione Lineare e alla Programmazione Lineare Intera, introducendo le principali metodologie e tecniche, come il Cutting Plane (in italiano, il Metodo dei Piani di Taglio) che hanno consentito di passare da 49 a 85.900 punti.

Un lettore appassionato di complessità computazionale troverà poi pane per i suoi denti nel capitolo apposito, dove Cook richiama le nozioni base della teoria per poter discutere la complessità del problema del commesso viaggiatore. Un altro capitolo è infine focalizzato sull’estetica e sull’arte. D’altronde, c’è molta bellezza nella matematica, e il TSP non smentisce assolutamente questo fatto, anzi. Cook riporta alcuni dipinti di Julian Lethbridge e dei murales di Philip Galanter.

Dipinto di Julian Lethbridge (fonte: https://users.encs.concordia.ca/~chvatal/tsp/tsp.html )

Un paragrafo è riservato a Robert Bosch, celebre per la sua “TSP Art”: chi l’avrebbe mai detto che la Monna Lisa fosse un problema NP-hard?

“Monna Lisa” come istanza del TSP con n = 100.000 punti (fonte – https://www.math.uwaterloo.ca/tsp/ )

Bosch ha inoltre riportato i suoi studi e le sue opere in “Opt Art: From Mathematical Optimization to Visual Design”. Ma, questo, è un altro libro.

In conclusione, tornando a “In Pursuit of the Traveling Salesman”, l’unico difetto che possiamo – per ora – trovare è il fatto che sia disponibile solo in lingua originale, ovvero in inglese. Però non fatevi spaventare e lasciate che Cook vi accompagni, con il suo stile chiaro e ricco di aneddoti, in questo tour ancora in corso.

Alla prossima recensione!

“In Pursuit of the Traveling Salesman.
Mathematics at the Limits of Computation”
William J. Cook
Editore: Princeton University Press
Anno edizione: 2014
In commercio dal: 09 novembre 2014
Pagine: 228 p., ill. , Brossura
EAN: 9780691163529