## 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

**Abstract:**

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(n*^{3}) time while the former, running in *O(n*^{6}) 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 + n*^{2}*log*(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**

**Abstract:**

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**

**Abstract:**

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.