Set-Covering: un'implementazione dell'algoritmo di Frank-Wolfe per risolvere il rilassamento lineare

The Set-Covering Problem, SCP for short, is a combinatorial optimization problem which consists in determining the smallest collection in a family of subsets, whose union equals a given set of elements, such that each one of these elements is covered by at least one subset in the selected collection. This problem, along with its variations, has numerous practical applications across multiple fields. For example, it is widely used in logistic to optimize resource management and distribution. It is also employed by airlines to streamline and optimize aircraft management and pilot work schedules. This work aims to produce an implementation of an algorithm based on the Frank-Wolfe method, in order to efficiently solve the SCP linear relaxation. The first part indroduces general concepts related to mathematical optimization and linear programming. Furthermore, it briefly describes the intuition behind the simplex algorithm and how it is employed to solve linear programming problems. Subsequently, the foundamental principles of the Frank-Wolfe algorithm are presented, along with a mathematical formulation of the Set-Covering Problem, to explore possible applications of the algorithm to the SCP linear relaxation. Finally, the analyzed algorithm is implemented and tested on different instances of the problem, in order to measure its running times and compare them with those produced by the simplex method for solving the same instances.

Il problema del Set-Covering (Set-Covering Problem, SCP) è un problema di ottimizzazione combinatoria che consiste nel determinare la più piccola collezione di elementi in una famiglia di sottoinsiemi di un insieme, in modo che ciascun elemento di quest'ultimo sia coperto da almeno un sottoinsieme all'interno di tale collezione. Questo problema, insieme alle varianti che ne derivano, ha numerose applicazioni pratiche in molteplici ambiti. Viene ad esempio impiegato nell'ambito della logistica per ottimizzare la gestione e la distribuzione delle risorse. Trova spazio anche all'interno delle compagnie aeree, dove viene utilizzato per semplificare e ottimizzare la gestione degli aerei e dei turni di lavoro dei piloti. Questo lavoro propone l'implementazione di un algoritmo basato sul metodo di Frank-Wolfe, con l'obiettivo di ricercare un modo efficiente di risolvere il rilassamento lineare del SCP. Nella prima parte vengono introdotte nozioni di carattere generale riguardanti l'ottimizzazione matematica e la programmazione lineare. Inoltre, vengono brevemente descritte l'intuizione alla base dell'algoritmo del simplesso e la modalità con cui questo algoritmo viene impiegato per risolvere problemi di programmazione lineare. Successivamente vengono presentate l'idea generale alla base dell'algoritmo di Frank-Wolfe e una formulazione matematica per il problema del Set-Covering, con l'obiettivo di analizzare l'applicazione di tale algoritmo al rilassamento lineare. Infine, viene sviluppata un'implementazione dell'algoritmo per risolvere diverse istanze del problema, accompagnata da un confronto con l'algoritmo del simplesso applicato alle stesse istanze.