Skip to main content


Thesis defences

PhD Oral Exam - Huy Quang Duong, Computer Science

Nested Column Generation for Optical Network Optimization

Date & time

Monday, July 27, 2020
10 a.m. – 2 p.m.


This event is free


School of Graduate Studies


Daniela Ferrer



When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.


Defragmentation/reoptimization of Elastic Optical Networks (EONs) reallocates connections to achieve an improved system, e.g., reducing the total required spare capacity or transmission delay. EONs comprise multiple layers which have different functionalities and management. This thesis studies two main layers of EONs that are Logical Layer and Optical Layer. Although defragmentation/reoptimization has many techniques and strategies, because of practical-application requirements, this work only discusses make-before-break (MBB) technique to reduce capacity/spectrum usage at defragmentation events predetermined by time-driven manner.

There are two directions in terms of solution strategies. In the first direction, network operator solves the original problem of finding the optimal state that MBB rerouting sequences can reach. This direction is hard to solve because MBB condition makes the problem complicated. In the second direction, it decomposes the problem into two steps. The first step computes the optimal state (target state) without MBB condition. And the second step finds a rerouting sequence to bring current state to the target state as close as possible under MBB condition. This direction is a heuristic because there is no assurance that network can reach the target state. However, this direction is easier to model and solve than the first direction.

For both directions, this work proposes several heuristic algorithms and sub-optimal algorithms using column generation for (nested) decomposition mathematical models. Our proposed models and algorithms enlarge the scalability of data sets in literature.

Back to top Back to top

© Concordia University