PhD Oral Exam - Yan Wang, Computer Science
Optimal design of filterless optical networks
This event is free
School of Graduate Studies
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.
Filterless optical network has been widely used in recent years. The incentive of this technology is only the passive equipment will be used, which requires no electricity. By using this technology, not only the cost reductions, but also the environment friendly will be achieved.
In literature, a lot of researchers studied the design of filterless optical network. But due to the complexity and scalability limits of this problem, most of their works are based on heuristic or meta-heuristic methods. We were seeking exact solutions to achieve the design of filterless optical networks.
First we proposed a one step solution scheme, which combines network provisioning, i.e., routing and wavelength assignment within a single mathematical model, called CG_FOP. Decomposition into two different types of sub-problems is then used in order to conceive an exact solution scheme. The first type of sub-problem relies on the generation of filterless subnetworks while the second one takes care of their wavelength assignment. The results from two pricing model were put back to the restricted master problem as configuration columns, in order to find exact solutions of the optimal network provisioning and wavelength assignment.
Due to the complexity of the problem, significant time will be consumed if applied our model on a large and more connected network. In order to improve the performance, we proposed Dantzig-Wolfe decomposition model, called DW_FOP, in which the sub-problem consists in generating a potential filterless optical sub-network, with a directed tree topology. In this new model, single pricing problem was formed which compute the network provisioning along with wavelength assignment together. In this way, master problem would be simplified, no longer contains complicated logic to build conflicts among requests. With this approach, CPU time significantly improved.
Furthermore, we continue to improve the design, proposed a nested column generation model, called FOP_NCG, in order to speed up solution process. We break down the solution into two level of pricing, the upper level pricing computing selected paths which assigned to granted requests, network provisioning and wavelength assignment for granted requests. The upper level pricing itself is a column generation process, which consists of a lower level pricing generated improved path for each granted requests. In order to get valid bound for our problem, Lagrangian relaxation technique was used to improve LP bound.
Numerical results are conducted on the networks which are widely referred in the literature.