Search

International audience; Worldwide telecommunications groups are both infrastructure operator and service provider. Hence, when planning the network expansion, these groups must also consider the subscribers dynamics, which they can influence through subsidies. Addressing both aspects together enables them to better optimize the network dimensioning, therefore avoiding unnecessary costs. In this work, the network expansion represents the deployment and/or reinforcement of several technologies (e.g. 2G,3G,4G), assuming that subscribers to a given technology can be served by this technology or older ones. The objective of the resulting optimization problem is to minimize network investments costs and subsides, while being subject to both capacity and strategical constraints, such as minimum coverage and users averaged throughput. We model the customer behavior in response to subsides with S-shape piecewise linear functions, which are linearized. We assess numerically the resulting Mixed-Integer Linear Programming (MILP) formulation on real-life instances focusing on 3G/4G migrations. Our results show the scalability of the MILP model for 2 network generations and 100 sites. Moreover, they underline the cost-benefit of solving a unique optimization problem over the whole time-horizon (5 years) compared to decomposing the problem year by year.

International audience; We discuss two approaches to approximate the convex and concave envelopes of bilinear functions over hypercubes. The first approach is based on a semidefinite program. The second approach considers some predefined cover sets of a hypercube and leads to a linear program. Then we establish a connection between the convex envelope of a bilinear function and the concave envelope of a piecewise linear function. Numerical experiments are conducted to compare the two approaches. As an extension, a novel approach is discussed

International audience; This paper focuses on the design of networks with unicyclic connected components. The size of each cycle should not be less than a given number. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Then the network design problem is solved by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroid.

International audience; To optimize the quality of service through a telecommunication network, we propose an algorithm based on Lagrangian relaxation. The bundle-type dual algorithm is adapted to the present situation, where the dual function is the sum of a polyhedral function (coming from shortest path problems) and of a smooth function (coming from the congestion function).

International audience

Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message routing problem in data networks, but it includes a broader literature overview of convex multicommodity flow problems. We present and discuss the main solution techniques proposed for solving this class of large-scale convex optimization problems. We conduct some numerical experiments on the message routing problem with four different techniques.

International audience; We propose a new method based on minimum mean cycle cancelling for multicommodity flow problems with separable convex cost ruling out saturated capacities. This method is inspired by the cycle cancelling method first worked out by Goldberg and Tarjan for minimum cost circulations (A.V. Goldberg, R.E. Tarjan, Finding minimum-cost circulation by cancelling negative cycles, JACM 36 (4), 1989, pp. 873–886). Convergence of the method is formally proved and a variant with a more flexible selection of cycles is proposed. Also, we report some computational experience on the message routing problem in telecommunication networks using actual and randomly generated networks.

One of the main problems in telecommunications is the robust network design under demand uncertainty. Having the network's architecture and a given budget for the capacity allocation problem, the aims is to identify a feasible capacity that minimizes the worst case of non-satisfying demand. Firstly, the demand's uncertainty is formulated as a convex hull defined by a finite number of scenarios. We prove that the problem can be rewritten as the minimization of a convex function over a polyhedral. So, an optimal solution is calculated using three cutting-plane methods: Kelley, Elzinga-Moore and Bundle. Then the uncertainty is formulated as a polyhedral described by a unite number of linear inequalities, which leads to a problem considerably more difficult. In consequence, we search only for upper and lower bounds. Some innovating ideas are presented and Falk & Soland Branch & Bound algorithm is used in order to calculate the maximum of an additive convex function; moreover, we define a variant of this algorithm, adapted to our particular problem. After having defined the network's design, the next step is to calculate the optimal routing in the network. The congestion is minimized using as objective function the Kleinrock delay function. The resulting problem is convex but non-linear and the dual function is the sum of a polyhedral function and of a smooth function. To solve this problem, a hybrid algorithm is implemented, based on Lagrangian relaxation.; Un des problemes majeurs dans le domaine des telecommunications est de construire des réseaux robustes qui puissent faire face a l'incertitude de la demande. Ayant l'architecture d'un réseau et un budget donne pour le problème d'allocation de la capacité, le but est d'identifier une capacité faisable, qui minimise le pire cas de demande insatisfaite. Premièrement, nous formulons l'incertitude de la demande comme un polytope engendre par un nombre fini de scénarios de la demande. Nous montrons que le problème peut se ramener a la minimisation d'une fonction convexe sur un polyèdre. Nous calculons alors une solution optimale par trois méthodes de plans sécants : Kelley, Elzinga & Moore et faisceaux. Ensuite, nous formulons l'incertitude comme un polyèdre décrit par un nombre fini d'inégalités linéaires, ce qui résulte en un problème considérablement plus difficile. Par conséquent, nous cherchons uniquement des bornes supérieures et inférieures. Quelques idées novatrices sont présentées et l'algorithme de type \Branch & Bound" de Falk & Soland est utilise afin de calculer le maximum d'une fonction convexe additive ; de plus, nous défifinissons une variante de cet algorithme, adaptée a notre situation particulière. Après avoir défini la capacité d'un réseau, l'étape suivante est de calculer le routage optimal dans ce réseau. Nous minimisons la congestion en utilisant comme objectif la fonction moyenne de retard de Kleinrock. Le problème résultant est convexe mais non-linaire et la fonction duale est la somme d'un terme polyédral et d'un terme différentiable. Afin de résoudre ce problème, nous implémentons un algorithme hybride base sur la relaxation Lagrangienne.