C'era un tempo in cui anche il Maestro era un matematico...

Recentemente mi è capitato di rileggere il documento di tesi che ho presentato durante la mia sessione di laurea in ingegneria informatica nel lontano 2007 e mi sono chiesto, incuriosito, se in questi quattro anni i risultati ottenuti dalla ricerca che avevo condotto sono stati migliorati da altre menti illuminate o se lo stato dell'arte attuale fosse lo stesso di quando io mi ero cimentato nell'ardua impresa di scuoterlo. E devo dire che non ho trovato nulla di nuovo all'orizzonte.

Il mio lavoro di tesi è nato con l'intento di sviluppare idee interessanti per la progettazione di un algoritmo in grado di risolvere il Multidimensional Knapsack Problem, uno dei problemi di tipo NP-Hard in forma Strong più noti e complessi in letteratura.
Al momento della stesura di questa tesi non esistevano algoritmi in grado di risolvere in modo esatto istanze particolarmente complesse del Multidimensional Knapsack Problem e la ricerca era attualmente direzionata verso strade euristiche, con lo scopo di fornire soluzioni di buona qualità in tempi ragionevoli.

Il fatto che, nonostante il problema fosse noto ormai dalla fine degli anni 60, non esistesse una vasta letteratura di metodologie efficaci per la sua risoluzione, mi ha motivato nello sviluppo di una strategia esatta per istanze di medie dimensioni da poter comunque adattare in modo euristico ad istanze più complesse, con lo scopo di competere con i risultati migliori recentemente ottenuti su istanze benchmark da un algoritmo Tabu Search.

Il Multidimensional Knapsack Problem è noto per la sua complessità: pur disponendo a posteriori di una soluzione vericata essere ottima, la certifica dell'ottimalità è un'operazione talmente ardua da richiedere diverse settimane di calcolo sulle macchine di ultima generazione.

Ma di cosa si tratta veramente?

Il Multidimensional Knapsack Problem (MKP) è un problema di ottimizzazione combinatoria che può essere formulato nel seguente modo:

 

Le variabili xj rappresentano gli n oggetti (o items) ognuno avente un prezzo pj e un peso wj . Il meccanismo risolutivo del problema definito sopra consiste nell'inserire all'interno di uno zaino avente capacità massima pari a c un sottoinsieme di oggetti in modo che venga massimizzato il prezzo totale degli stessi senza violare il vincolo di capacità dello zaino.
Il MKP è un problema dello zaino m-dimensionale nel senso che è soggetto contemporaneamente a m vincoli di capacità distinti. Ogni oggetto j è caratterizzato da un prezzo pj e da m pesi wij che variano in relazione allo zaino in cui vengono inseriti.
Selezionare un oggetto j (quindi porre xj = 1) corrisponde a doverlo inserire in tutti gli m zaini del problema. L'obiettivo della risoluzione del MKP è sempre quello di massimizzare il prezzo totale del set di oggetti selezionati con l'unica differenza che tale sottoinsieme di oggetti deve poter essere inserito in ogni zaino senza che ne venga ecceduta la relativa capacità.

La mia ricerca mi ha occupato per un intero anno in cui ho voluto progettare un algoritmo originale e funzionale al problema, allontanandomi dal percorso più o meno standard di chi era intento a perfezionare strumenti risolutivi affermati nel campo quali tabu search, simulated annealing, algoritmi genetici e quant'altro.

Il risultato prodotto è un algoritmo modulare che ha permesso di risolvere all'ottimo istanze con un numero di vincoli ridotti e note in letteratura per la complessità di risoluzione. La cosa interessante è che all'aumentare dei vincoli l'algoritmo può essere utilizzato in modo euristico andando a fornire una buonissima soluzione senza tuttavia avere la certezza di essere la migliore. Dopotutto si tratta pur sempre di un problema NP-Hard e non ho mai avuto la presunzione di poterlo risolvere in modo polinomiale anche perchè, se lo avessi fatto, avrei risolto uno dei 7 problemi matematici irrisolti del millennio!

Se dovessi descrivere in poche righe l'algoritmo da me ideato potrei utilizzare l'espressione di riduzione ricorsiva di un problema core mediante l'applicazione di una funzione di valutazione adattativa delle soluzioni di base per determinare il fixing diretto e indiretto delle variabili. Chiaro no? Beh, dopotutto se fossi riuscito a sintetizzare un tomo di 100 pagine pieno di formule matematiche e dimostrazioni logiche in 3 righe mi avrebbero come minimo dovuto consegnare la laurea in lettere ad honorem!

In finale, i risultati sono soddisfacenti? Direi che non mi posso lamentare visto che è stato il primo algoritmo [EC] a risolvere in modo esatto le istanze di Chu  & Beasley [38] ben note in letteratura per la loro complessità e ha avvicinato in termini di bontà l'euristica proposta da Vasquez e Vimont [39] in tempi decisamente inferiori.

Sono sicuro che, applicando l'algoritmo per la stessa durata di esecuzione di Vasquez, l'algoritmo EC da me proposto avrebbe per lo meno eguagliato gli stessi suoi risultati. Con la differenza che l'euristica è stata la parte meno approfondita della mia ricerca e notevolmente migliorabile, essendomi  preso pure la libertà di sottolineare le modalità per farlo. Ahimè non ho avuto tempo di processare l'algoritmo per 40 giorni consecutivamente....

Avrei potuto continuare la mia attività di ricerca in Università, concentrandomi sulla risoluzione di quello che non solo è uno dei problemi più stimolanti per la comunità matematica ma anche un problema con interessanti applicazioni pratiche, vedasi le aste combinatorie. Non ho avuto il coraggio di affrontare questa sfida in un paese notoriamente avvezzo a non promuovere la ricerca. La mia sfiducia in tal senso era così elevata che non ho pubblicato nemmeno la mia ricerca, lasciando all'ateneo ogni libertà sull'approfondirla in seguito. Non ho idea se lo abbiano fatto o meno, probabilmente nemmeno l'avranno capita. Quello che posso fare ora che sono troppo arrugginito per riprendere in mano questi studi è rendere disponibile il mio lavoro, sperando che i posteri ne possano trarre vantaggi ai fini della ricerca.

Download di Multidimensional Knapsack Problem - EC Algorithm