[Todos CMAT] Defensa de Tesis de Doctorado PEDECIBA Informática: Gabriel Bayá / miercoles 25 de Octubre, 14hs, salón Azul.

[frobledo]

Estimados investigadores, estudiantes y docentes:

Nos complace invitar a asistir a la defensa pública de la tesis de  
Doctorado de PEDECIBA Informática del MSc. Ing. Gabriel Bayá Mantani.  
A continuación se incluye información detallada al respecto:

Día: miercoles 25 de octubre de 2017.

Hora: 14hs.

Lugar: salón Azul, piso 5 Cuerpo Central, Facultad de Ingeniería, UdelaR.

Título de la tesis: "Topological Design of Survivable Networks".

Directores de Tesis: Dr. Franco Robledo y Dr. Antonio Mauttone.

Director Académico: Dr. Franco Robledo.

Tribunal:

- Dr. Guillermo Durán, Director del Instituto de Cálculo, Universidad  
de Buenos Aires, Argentina. - REVISOR.
- Dr. Eduardo Moreno, Facultad de Ingeniería y Ciencia, Universidad  
Adolfo Ibáñez, Chile. - REVISOR.
- Dr. Víctor Albornoz, Departamento de Industrias, Universidad  
Federico Santa María, Chile.
- Dr. Ing. Pablo Rodríguez-Bocca, Departamento de Investigación  
Operativa, Instituto de Computación, Facultad de Ingeniería, UDELAR.
- Dr. Ing. Eduardo Fernández, Centro de Cálculo, Instituto de  
Computación, Facultad de Ingeniería, UDELAR.



Abstract:
In the field of telecommunications there are several ways of  
establishing links between different physical  places that must be  
connected according to the characteristics and the type of service  
they should provide. Two main considerations to be taken into account  
and which require the attention of the network planners are, in one  
hand the economic effort necessary to build the network, and in the  
other hand the resilience of the network to remain operative in the  
event of failure of any of its components. A third consideration,  
which is very  important when quality of services required, such as  
video streaming or communications between real-time systems, is the  
diameter constrained reliability. In this thesis we study a set of  
problems that involve such considerations.

Firstly, we model a new combinatorial optimization problem called  
Capacitated m-Two Node Survivable Star Problem (CmTNSSP). In such  
problem we optimize the costs of constructing a network composed of  
2-node-connected components that converge in a central node and whose  
terminals can belong to these connected 2-node structures or be  
connected to them by simple edges. The CmTNSSP is a relaxation of the  
Capacitated Ring Star Problem (CmRSP), where the cycles of the latter  
can be replaced by arbitrary 2-node-connected graphs.  According to  
previous studies, some of the structural properties of  
2-node-connected graphs can be used to show a potential improvement   
in construction costs, over solutions that exclusively use cycles.  
Considering that the CmTNSSP belongs to the class of NP-Hard  
computational problems, a GRASP-VND metaheuristic was proposed and  
implemented for its approximate resolution, and a comparison of  
results was made between both problems (CmRSP and CmTNSSP) for  a   
series of instances. Some local searches are based on exact Integer  
Linear Programming formulations. The results  obtained show that the  
proposed metaheuristic reaches satisfactory levels of accuracy,  
attaining the global optimum in several instances.

Next, we introduce the Capacitated m Ring Star Problem under Diameter  
Constrained Reliability (CmRSP-DCR) wherein DCR is considered as an  
additional restriction, limiting the number of hops between nodes of  
the CmRSP problem and establishing a minimum level of network  
reliability. This is especially useful in networks that should  
guarantee minimum delays and quality of service. The solutions found  
in this problem can be improved by applying some of the results  
obtained in the study of the CmTNSSP.

Finally, we introduce a variant of the CmTNSSP named Capacitated  
Two-Node Survivable Tree Problem, motivated by another combinatorial  
optimization problem most recently treated in the literature, called  
Capacitated Ring Tree Problem (CRTP). In the CRTP, an additional  
restriction is added with respect to CmRSP, where the terminal nodes  
are of two different types and tree structures are also allowed. Each  
node in the CRTP may be connected exclusively in one cycle, or may be  
part of a cycle or a tree indistinctly, depending on the type of node.  
In  the variant we introduced, the cycles are replaced by  
2-node-connected structures. This study proposes and  implements a  
GRASP-VND metaheuristic with specific local searches for this type of  
structures and adapts some of the exact local searches used in the  
resolution CmTNSSP. A comparison of the results between the optimal  
solutions obtained for the CRTP and the CTNSTP is made. The results  
achieved show the robustness and efficiency of the metaheuristic


Keywords: Network Optimization, Diameter Constrained Reliability,  
CmRSP, CmTNSSP, CRTP, CTNSTP, GRASP, VND.