Models and algorithms for the Euclidean Steiner tree problem

The Euclidean Steiner tree problem (ESTP) consists in finding the shortest network inter connecting p given points, using additional points when beneficial. This problem belongs to the set of NP-Hard problems, and it is prohibitive to find an optimal solution in a reasonable time for large instances. In this context, we apply Benders decomposition, a mathematical programming technique that allows a problem to be decomposed into two subproblems, the Master and the Subproblem, to a formulation given in the literature. The main objective is to understand if it is possible to get better results in terms of times and nodes explored by Branch and Cut methods with respect to solving the entire formulation. In particular, two versions of this problem have been explored, with different types of complicating variables. For Benders decomposition, we explore the classical version using the cutting plane method, in which the feasible region of the Master problem is dynamically refined through Benders cuts. Then we integrate it in a Branch and Bound approach, getting a Benders Branch and Cut (BBC) approach. In this second method, we add Benders cuts during the Node exploration of Master problem. The best results are obtained with Benders Branch and Cut. What is observed is that the execution between solving the decomposition and solving the entire formulation, using the commercial solver FICO Xpress, seems comparable, if the entire formulation is solved with the preprocessor activated. Instead, if the preprocessor is deactivated, as we need to do with BBC approach for the structure of FICO Xpress, the results of Benders decomposition are better with respect to solving the entire formulation.

Il problema dell’albero di Steiner Euclideo (ESTP) consiste nel trovare l’albero più corto per collegare p punti, usando punti addizionali se necessario. Questo problema appartiene alla classe dei problemi NP-difficili e di conseguenza non è possibile trovare una soluzione ottima in un tempo ragionevole per istanze non banali. In questo lavoro è stato applicato una Decomposizione di Benders, che permette di scomporre un problema in 2 sottoproblemi, il problema Master e il Subproblem, alla formulazione in programmazione matematica della letteratura recente. L’obbiettivo è quello di comprendere se è possibile ottenere un miglioramento in termini di tempo e di nodi esplorati dell’albero di Branch and Cut rispetto a risolvere la formulazione per intero. Sono state sviluppate due diverse tipologie di decomposizioni di Benders, considerando due diverse variabili complicanti. Per la decomposizione di Benders sono stati usati sia la versione tramite metodo dei piani di taglio, nel quale viene ristretta dinamicamente la regione di fattibilità di uno dei sotto problemi, sia una versione integrata in un Branch and Bound chiamata Benders Branch and Cut (BBC), dove i tagli di Benders vengono aggiunti direttamente ai nodi esplorati. I risultati migliori, a livello computazionale, sono stati ottenuti tramite il metodo Benders Branch and Cut, ma è stato possibile osservare che la risoluzione con la decomposizione e la risoluzione della formulazione intera, utilizzando il risolutore commerciale FICO Xpress con il preprocessor attivato, hanno avuto risultati comparabili. Invece, nel caso in cui per la formulazione intera il preprocessor di FICO Xpress sia impostato a 0, cosa invece necessaria per l’implementazione del metodo BBC, i risultati mostrano che l’approccio Benders Branch and Cut risulta migliore rispetto a risolvere la formulazione per intero.