[Todos CMAT] Defensa de Tesis de Doctorado PEDECIBA Informática: Gabriel Bayá / miercoles 25 de Octubre, 14hs, salón Azul.
frobledo
frobledo en fing.edu.uy
Dom Oct 8 23:37:06 -03 2017
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.
Más información sobre la lista de distribución Todos