Bottleneck optimum communication spanning tree problems

In recent years, much interest has been focused on various problems that arise in the area of network design. We consider the Optimum Communication Spanning Tree Problem (OCSTP), which is defined as follows. Given a complete undirected graph with a cost associated to each edge and a communication requirement between each pair of nodes, find a spanning tree connecting all the nodes which minimizes the total communication cost, i.e. the sum of the communication costs over all pairs of nodes. This classic problem has been extensively studied in the literature and it is not applied only in the network design area for transportation planning and communication system planning, but also, for example, in the alignment of genomic sequences and in hub allocation. In this work we investigate two variants of the OCSTP, with a different objective function. In the Minimum Path Optimum Communication Spanning Tree Problem (MP-OCSTP) the objective is to find a spanning tree where the cost of most expensive path between a pair of nodes is minimum. In the Minimum Edge Optimum Communication Spanning Tree Problem (ME-OCSTP) the objective is to find a spanning tree where the cost of the most expensive edge is minimum. These problems are relevant in some applications. First, we study some special cases of MP-OCSTP in which the optimal solutions have a known structure. In particular, we show that, if the costs and the requirements are all equal, any optimal solution is a star-tree. Then, we propose three Mixed Integer Linear Programming models for these problems. The main feature that distinguishes the formulations is the number of indeces of the considered variables: 4-index, 3-index and 2-index. The computational results obtained on benchmark instances from the literature show that a large computing time is required to solve the ME-OCSTP to optimality. Instead, to solve the MP-OCSTP the computational times are quite reasonable. After evaluating the quality of the linear relaxation bounds, we also propose some valid inequalities for the different formulations. When necessary, the valid inequalities are generated by solving the corresponding separation problem. The computational results indicate that for MP-OCSTP all the formulations provide good solutions with an equivalent objective function value for all the instances satisfying the triangular inequality, while the 4-index formulation outperforms the other two formulation on randomized instances. For the ME-OCSTP the linear relaxation of 2-index formulation is more competitive than the other two, but this problem turn out to be very challenging. In most of the cases the valid inequalities do not lead to substantial improvements. Finally, we present some heuristic algorithms. Greedy algorithms are based on the minimum spanning tree, or on the star-trees or on the Gomory-Hu tree. The local-search algorithm for the MP-OCSTP tries to connect directly the end-nodes of the most expensive path and to delete one of the edges in the generated cycle. Instead, for the ME-OCSTP the local-search algorithm tries to delete the most expensive edge and to add one of the edges that connects the two disconnected components. The results show that the heuristic combining the greedy algorithm based on the Gomory-Hu tree and the local-search algorithm, provides the best upper bound on many instances for both problems. We also develop a randomized version of the algorithm based on the Gomory-Hu tree, which yields improved solutions.

Negli ultimi anni, un crescente interesse è stato rivolto a problemi appartenenti all'area del network design. Considereremo l'Optimum Communication Spanning Tree Problem (OCSTP), che è definito come segue. Dato un grafo completo non direzionato con una funzione Costo definita per ogni arco e una funzione Domanda definita per ogni coppia di nodi, si vuole costruire lo spanning tree che minimizza il costo totale di comunicazione, ottenuto come la somma di tutti i costi dell'albero. Questo problema è stato ampiamente studiato e trova applicazione non solo nell'area del network design per la pianificazione di trasporti o di sistemi di comunicazione, ma anche, per esempio, nell'allineamento di sequenze di DNA e nell'allocazione di Hub. In questa tesi presentiamo due possibili varianti dell’OCSTP. Nel Minimum Path Optimum Communication Spanning Tree Problem (MP-OCSTP) si vuole minimizzare il costo del cammino più costoso per connettere una coppia di nodi. Invece, l'obiettivo del Minimum Edge Optimum Communication Spanning Tree Problem (ME-OCSTP) è quello di minimizzare il costo dell'arco più costoso. Queste due varianti hanno rilevanza in alcune applicazioni. Innanzitutto, proporremo uno studio della struttura che la soluzione assumerebbe sotto alcune ipotesi particoli. Per quanto riguarda il MP-OCSTP mostreremo che quando i costi e le domande sono tutti uguali tra loro ogni soluzione ottima assume la forma di una stella. Poi, presenteremo tre modelli di programmazione mista intera. Ogni modello si distingue dagli altri per il numero di indici delle variabili scelte: 4-indici, 3-indici e 2-indici. Per quanto riguarda il ME-OCSTP con istanze note in letturatura si vede che ottenere la soluzione ottima richiede un tempo computazionale elevato, mentre il MP-OCSTP è risolvibile in tempi più ragionevoli. Dopo aver valutato la qualità dei bound ottenuti con il rilassamento lineare, proporremo alcune disuguaglianze valide. Aggiungeremo quest'ultime risolvendo, quando necessario, un problema di separazione. I risultati computazionali indicano che per il MP-OCSTP tutte le formulazioni portano a buoni risulati con un equivalente valore della funzione obiettivo quando le istanze soddisfano la disuguaglianza triangolare; mentre con istanze che non la soddisfano la formulazione con variabili a 4 indici risulta migliore. Per il ME-OCSTP la formulazione con variabili a 2 indice è più competitiva delle altre, nonostante i risultati siano meno soddisfacenti rispetto a quelli ottenuti per l'altro problema. Vedremo anche che in alcuni casi le disuguaglianze valide non migliorano i risultati ottenuti senza di esse. Infine introdurremo alcune euristiche: le greedy saranno basate sul Minimum Spanning Tree, sulle stelle o sull'albero di Gomory-Hu, la ricerca-locale per il MP-OCSTP proverà a collegare i due nodi con il cammino più costoso in modo diretto, andando poi ad eliminare un arco nel ciclo che si genera e la ricerca locale per il ME-OCSTP proverà ad eliminare l'arco più costoso sostituendolo con un'altro che connetta le due componenti sconnesse. I risultati ottenuti mostrano che l'euristica basata sull'albero di Gomory-Hu, vista come il greedy più la ricerca locale, è la migliore per entrambi i problemi con molte istanze. A conclusione proveremo ad applicare proprio all'euristica basata sull'albero di Gomory-Hu una procedura randomizzata (GRASP), con la quale si otterrano soluzioni migliori.