Tecniche di Column Generation per problemi di Robust Network Design

In questo elaborato si vogliono presentare delle tecniche basate sul column generation per la risoluzione di un problema di Robust Network Design (RNDP). Il RNDP ha l’obiettivo di stabilire le connessioni di una rete di comunicazione in modo che questa sia robusta al failure di un tratto. Nella pratica, significa progettare una rete che, prevedendo delle connessioni di backup, riesca a non interrompersi a seguito del guasto di un tratto della rete. Volendo minimizzare l’occupazione delle risorse di rete, si implementa un modello di ottimizzazione per la ricerca di una soluzione ottimale al RNDP. Il modello, tuttavia, prevede l’utilizzo di un numero troppo grande di variabili, e quindi si ricorre all’uso del column generation per costruire un modello ridotto (ma esatto e completo) con il quale trovare la soluzione ottimale del problema. L’algoritmo di column generation presentato nell’elaborato è composto da due diverse tipologie di risoluzione del sub problem: risoluzione euristica e risoluzione tramite modello di ottimizzazione. Si pone particolare attenzione alle tecniche euristiche, che si basano sull’utilizzo dell’algoritmo di Yen per la ricerca dei k cammini minimi e sull’utilizzo di un algoritmo di local search. L’algoritmo per la risoluzione del RNDP è implementato in un programma, del quale vengono analizzati le caratteristiche tecniche e le performance.