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.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.