Abstract The routing and spectrum assignment problem in modern optical networks is an NP‐hard problem that has received increasing attention during the last years. The majority of existing integer linear programming models for the problem uses edge‐path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. To bypass this difficulty, precomputed subsets of all possible paths per demand are typically used, which cannot guarantee optimality of the solutions in general. Our contribution is to provide a framework for the use of edge‐path formulations to minimize the spectrum width of a solution. For that, we select an appropriate subset of paths to operate on with the help of combinatorial properties in such a way that optimality of the solution can be guaranteed. Computational results indicate that our approach is indeed promising to solve the routing and spectrum assignment problem.

The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer programming formulations for RSA is the DR-AOV formulation, presented in a previous work. In this work we explore a relaxation of this formulation with a subset of variables from the original formulation, in order to identify valid inequalities that could be useful within a cutting-plane environment for tackling RSA. We present basic properties of this relaxed formulation, we identify several families of facet-inducing inequalities, and we show that they can be separated in polynomial time.

The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years.Existing integer linear programming models for the problem are either very complex and suffer from tractability issues or are simplified and incomplete so that they can optimize only some objective functions.The majority of models uses edgepath formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance.An alternative is to use edgenode formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance.However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions.Our contribution is to provide the first complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model.Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t.several objective functions.We further devise some directions of future research.

Given an undirected graph G, a specific node r, and capacity on the nodes, the maximum bounded r-tree problem consists of finding a tree of G rooted at r containing as many nodes as possible with respect to the node capacities. This NP-hard optimization problem has been recently considered in the context of peer-to-peer networks. In this work, we study the associated polytope, in the space of edge variables. We introduce several families of facet-defining inequalities which lead to complete polyhedral descriptions of the polytope as well as total dual integrality of the defining linear system on trees and cycles. We also address their separation problems and present some preliminary computational results obtained by our branch-and-cut algorithm.

This paper deals with the survivable network design problem where each node v has a connectivity type $r(v)$ equal to 1 or 2, and the survivability conditions require the existence of at least $\min\{r(s),r(t)\}$ edge-disjoint paths for all distinct nodes s and t. We consider the polytope given by the trivial and cut inequalities together with the partition inequalities. More precisely, we study some structural properties of this polytope which leads us to give some sufficient conditions for this polytope to be integer in the class of series-parallel graphs. With both separation problems for the cut and partition inequalities being polynomially solvable, we then obtain a polynomial time algorithm for the (1,2)-survivable network design problem in a subclass of series-parallel graphs including the outerplanar graph class. We also introduce a new class of facet-defining inequalities for the polytope associated to the (1,2)-survivable network design problem.

Abstract For the past few decades, combinatorial optimization techniques have been shown to be powerful tools for formulating and solving optimization problems arising from practical situations. In particular, many network design problems have been formulated as combinatorial optimization problems. With the advances of optical technologies and the explosive growth of the Internet, telecommunication networks have seen an important evolution and therefore designing survivable networks has become a major objective for telecommunication operators. Over the past years, much research has been carried out to devise efficient methods for survivable network models, and particularly cutting plane based algorithms. In this paper, we attempt to survey some of these models and the optimization methods used for solving them. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(1), 1–21 2005

In this paper we focus on the single-facility capacitated survivable network design problem. We optimize simultaneously the network topology and the link dimensioning in order to route all traffic commodities according to survivability requirements. The latter are actually expressed in terms of the spare capacity required to address link failures in the context of different rerouting strategies. We present a mixed-integer linear programming model solved by combining several approaches. To tackle the high dimensionality and to separate the continuous and integer variables, we use Benders' decomposition and a cutting-plane approach. Going beyond the proposed method itself, we examine and compare two well-known restoration techniques: local and end-to-end reroutings. Numerous computational results for realistic network instances provide a comparison of these rerouting mechanisms in terms of installed capacities, network density as well as overall costs and CPU time.