Thursday, 13:45 - 14:10 h, Room: H 3503


Elena Fernandez
A compact formulation for the optimum communication spanning tree problem

Coauthors: Carlos Luna Mota, Gerhard Reinelt


The optimum communication spanning tree problem (OCSTP) is a difficult combinatorial optimization problem with multiple applications in telecommunications and transportation. In the OCSTP communication requirements rij exist between pairs of nodes, and the communication cost between i, j, over a given spanning tree T, depends on rij and on the distance on T between i and j. Looking for a balance between construction and communication costs, the objective in the OCST is to find a spanning tree of minimum total communication cost. We present a formulation with two index decision variables, which models any partial order as a rooted tree. We further specialize the above formulation to model the OCSTP, by incorporating additional decision variables to represent the distance on the tree between pairs of nodes. We discuss some properties and reinforcements of the formulation, which is compared with a classical formulation with four index variables. Some numerical computational results are presented and analyzed.


Talk 2 of the contributed session Thu.2.H 3503
"Paths, trees and flows" [...]
Cluster 23
"Telecommunications & networks" [...]


  Do you need Missouri Loans Online as soon as possible? But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.