Frank Wolfe Method for Set Cover Problem with Lagrangian Relaxation

This thesis is an investigation for the application of the Frank-Wolfe Method to the Lagrangian Relaxation of the Set Cover Problem, a classical combinatorial optimization problem with several applications. The study goes about with a literature review starting from the foundational papers on the Frank-Wolfe al- gorithm and on Lagrangian Relaxation. The Frank-Wolfe method has numerous applications and is often preferred for it s fast iterations and for being projection free, resulting in lower compu- tational requirements. Lagrangian Relaxation gives a generic framework for computing lower bounds on the optimal value of an optimization problem. The thesis then introduces the Set Cover Problem, its mathematical formu- lation and its practical relevance in real world applications. Finally, the thesis shows how to apply the Frank-Wolfe method to the Lagrangian dual of the set cover problem, yielding an alternative method for computing the linear pro- gramming relaxation of the set cover problem.

Questa tesi e unindagine sullapplicazione del metodo di Frank-Wolfe al rilassa- mento lagrangiano del problema del set cover, un problema classico di ottimiz- zazione combinatoria con molteplici applicazioni. Lo studio prosegue con una revisione della letteratura a partire dai concetti fondamentali di algoritmo di Frank-Wolfe e rilassamento lagrangiano. Il Metodo di Frank-Wolfe ha numerose applicazioni e viene spesso scelto per le sue iterazioni veloci e l’assenza di proiezioni, che risultano in minori requisiti computazionali. Il rilassamento lagrangiano fornisce invece un metodo per il calcolo di approssimazioni inferiori al valore ottimo di un problema di ottimiz- zazione. La tesi prosegue introducendo il problema del set cover, la sua formulazione matematica e la sua rilevanza pratica nel mondo reale. Infine viene mostrato come applicare il metodo di Frank-Wolfe per la risoluzione del lagrangiano duale del problema del set cover, ottenendo un metodo alternativo per risolvere il suo rilassamento lineare.