Contributed Session Tue.3.H 3002

Tuesday, 15:15 - 16:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Communication network design


Chair: Youngho Lee



Tuesday, 15:15 - 15:40 h, Room: H 3002, Talk 1

Marc Ruiz
Multi-constructive meta-heuristic for the metro areas design problem in hierarchical optical transport networks

Coauthors: Jaume Comellas, Luis Velasco


Optical connections in flexgrid-based optical networks will be able to convey up to 1,Tbps in the near future. Before designing those core networks however, it is required to introduce some hierarchy defining metropolitan areas so to reduce the number of locations participating in the core network. Those areas are then interconnected through the core network, and so expenditure costs of the latter can be dramatically reduced by minimizing the amount of traffic to be handled. As a result of the problem complexity we propose an iterative meta-heuristic that, at each iteration, builds a feasible solution by applying either a greedy-randomized or a pure random constructive procedure. To reach local optima, a local search procedure is afterwards applied. Finally, diversification is exploited by applying path-relinking between new and elite solutions. The performance of single and multi-constructive meta-heuristics was compared against exact solutions obtained from an ILP model. Finally, a real instance from a nation-wide network operator was solved.
This work was supported by the Spanish science ministry through the TEC2011-27310 ELASTIC project.



Tuesday, 15:45 - 16:10 h, Room: H 3002, Talk 2

Jonad Pulaj
Models for network design under varied demand structures

Coauthor: Anastasios Giovanidis


Recent developments in capacitated network design encourage further generalizations of the problem over finite time periods. Thus, the multiperiod network design problem (MNDP) consists in (1) establishing the network topology, (2) installing capacities, and (3) routing communication demands, while taking into account the fluctuations of demands over the design time horizon and minimizing installation costs. In this talk, we present new models and solution algorithms for the MNDP. Among other useful techniques, we derive lower bounds using Lagrangian relaxation and examine approximation algorithms. We evaluate the effectiveness of our new approaches through computational experience conducted on a number of networks, including realistic instances derived from the survivable network design library (SNDLib). This work is developed as part of a joint German-Polish project on multiperiod network optimization. The goal of the project is to develop efficient mathematical models for capacity expansions over finite time periods.



Tuesday, 16:15 - 16:40 h, Room: H 3002, Talk 3

Youngho Lee
A nonlinear mixed integer programming problem in designing local access networks with QoS constraints.

Coauthors: Chanwoo Park, Gigyoung Park, Junsang Yuh


In this talk, we present nonlinear mixed integer programming models for solving the local access network design problem with QoS constraints. The problem is a two-level hierarchical location-allocation problem on the tree topology of local access networks. The objective function of the problem minimizes the total cost of fiber link and switches, while satisfying both the capacity of switches within the prescribed level of quality of service. In developing an exact optimal algorithm, we develop a new approach of the reformulation linearization technique (RLT) by linearizing the nonlinear QoS constraints by implementing mixed-integer linear constraints with auxiliary variables. By exploiting the special structure of the problem, we devise an outer approximation algorithm that implements cut generation strategies for cutting off the violated solution at each iteration. Computational results are presented for demonstrating the effectiveness of cut generation strategies.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra Sale? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.