Invited Session Thu.3.H 3002

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

Cluster 23: Telecommunications & networks [...]

Network design


Chair: Ridha Ali Mahjoub



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

Viet Hung Nguyen
A direct algorithm for detecting negative cost cycles in undirected graphs


Given an undirected, arbitrarily weighted graph G=(V,E) with n=|V| and m=|E|. We consider the problem of checking
whether G contains a negative cost cycle (UNCCD). It is known that the corresponding problem in directed graphs (NCCD) can be solved by
applying directly the Bellman-Ford algorithm. The UNCCD problem is much harder than the NCCD problem.
In our knowledge, for solving the UNCCD, there is no direct algorithm and we should reduce it to either the b-matching problem or
the T-join problem in some extended graphs derived from G. The latter reduction runs in O(n3) time while the former, running in O(n6) time, is less efficient.
In this paper, we improve the time complexity by giving a direct algorithm for the UNCCD problem which runs in O(mn + n2log(n)) time.
The algorithm, which is based on a polyhedral characterization of the cone of circuit by Seymour, is a variant of Edmonds' blossom algorithm for matching.



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

Amal Benhamiche
On the optical multi-band network design problem

Coauthors: Ali Ridha Mahjoub, Nancy Perrot, Eduardo Uchoa


User demand in traffic is steadily increasing and telecommunication operators are now interested in high bandwith capacitated networks to upgrade the transmission capacity of optical backbone networks. This evolution leads to a new variant of multi-layer network design problemĀ : the optical multi-band network design (OMBND) problem. It consists in selecting the minimum number of subbands to install on the virtual layer so that the traffic can be routed and there exists a path in the physical layer associated to each subband. We propose a path formulation based on an implicit model for the problem and describe some additional valid inequalities. We then present a column generation procedure to solve the linear relaxation of OMBND that uses a two-stage pricing problem. The column generation procedure is embedded in a branch-and-price approach with a specific branching rule to derive an integer solution. Some computational results are presented for realistic instances of network and illustrate the efficiency of this approach to solve huge instances.



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

Raouia Taktak
Models and algorithms for the survivable multilayer network design problem

Coauthors: Sylvie Borne, Virginie Gabrel-Willemin, A. Ridha Mahjoub


We are interested with the problem of survivability of the WDM layer in bilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, our purpose is to search the corresponding survivable topology in the WDM layer.
We give two integer formulations for the problem. The first one uses cut constraints and the second is a path-based formulation. We discuss the polyhedron associated to the cut formulation and introduce some valid constraints. We also discuss the pricing problem and the branching strategy for the path formulation. We finally present primal heuristics and give some experimental results for the two formulations.


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.