Search

International audience; We consider an offshore wind farm defined by the location of the wind turbines and the amount of energy supplied per turbine, as well as the location of the central station responsible for redistributing the collected energy to users on the power grid. Knowing the power injected at each node, the capacities, susceptance and costs of the cables that can be used, the goal is to determine the least expensive cabling to route the energy supplied by the wind turbines to the central station. This cabling must respect the capacity constraints on the cables as well as the electrical constraints of Load Flow defined at each node of the network. In a second step, we look for a cabling that is also robust in case of failure of a cable, the notion of robustness being seen here as the protection again the worst case of failure. This work was carried out in collaboration with EDF Energies renouvelables. We give a mathematical model of the problem taking into account all the constraints of capacity, connectivity, load flow, cable types and incompatibility between edges, in the form of a mixed integer quadratic program that can be linearized and solved using a MIP solver. We then propose two mathematical models for the robust problem, formulation inspired by the previous one and a bi-level program where the second level is a max min program. Finally we present the results of our tests which provide solutions for real data up to about 50 nodes, before concluding.

International audience

International audience

International audience; Discrete tomography deals with the reconstruction of discrete homogenous objects from their projections. The reader is referred to the book of Hermann and Kuba [2] for an overview on discrete tomography. The image reconstruction problem is important since its solution is required for developing efficient procedures in image processing, data bases, crystallography, statistics, data compressing,... It can be formulated as follows: given a rectangular array where entries represent the pixels of a digitalized image coloured with k different colors, we consider the problem of reconstructing an image from the number of occurrences of each colour in every column and in every row. The problem is known to be polynomial for k=1, NP-complete for k=3 [1] and its complexity is still open for k=2. Here, we shall consider a graph colouring problem which generalizes both the well known basic graph colouring problem and the above image reconstruction problem. We are given a graph G=(V,E) and a collection P of p subsets Pi of vertices of G. We are also given a set of colours 1, 2, ..,k as well as a collection of p vectors h(Pi) of integers. The problem is to find a k-partition, i.e. a k-colouring, of V such that the number of vertices of Pi coloured with colour j is equal to the jth entry of the vector h(Pi), for all j=1,..,k and all i=1,..,p. The basic graph colouring problem deals with different colour assigned to adjacent vertices: we will call this a "proper" k-colouring otherwise we will call this simply a k-colouring. In this talk, we will consider colouring as well as proper colouring. Let us consider the special case where the graph G is a grid graph, the vertices, denoted by Xrs, are located on row r and column s, r=1,..,m and s=1,..,n, and P is the collection of the m+n chains corresponding to the rows and columns: the problem of finding a k-colouring of G corresponds exactly to the image reconstruction problem. In this talk we will consider some extensions by taking more general classes of graphs such as trees or bipartite graphs. We will restrict our attention to the case where each Pi is a chain in G. We call "cover index" of P, c(P), the maximum number of members of P which may cover a single element of V, i.e. which have a non empty intersection. We call "nested" a family P such that, for any pair of subsets, either one subset is included in the other or they are disjoint; then, the "nesticity" of P, nest(P), is the smallest number of nested families in a partition of P into nested families. First we will give several basic conditions for a solution to exist. Then, we will classify the problems according to the number of colours, the values of c(P) and nest(P), the class of the graph, the diameter of the graph, and so on. For each problem, either we will propose a polynomial time algorithm or we will give complexity results. For instance, we will prove that when G is a tree, the 2-colouring problem and the proper 3-colouring problems are NP-complete even if the maximum degree of G is bounded by 3; but we will propose a polynomial time algorithm solving the k-colouring problem when G is a tree and when any two Pi intersect in at most one vertex. All our results will be summarized in a table.

International audience

International audience

In a graph G = (V, E) a subset F of V is a d-extensible set if for any stable set Sof F with |S|= d it exists a stable set S' of V-FF such that SUS' is a maximum stable set of G.We say that S can be extended to a maximum stable set with vertices outside of F, shortly S can be extended. We present a characterization of the d-extensible sets for the class of bipartite graphs and we determine, for some values of d, the maximum cardinality of a d-extensible set.We also determine the maximum cardinality of a d-extensible set for a subclass of arborescenceswhere any vertex x of V belongs to a maximum stable set. This problem has some applicationsin reliability where we consider vertex failures in the graph G : a d-extensible set is the set ofvertices that are not protected.

Nous étudions la résolution d'un programme linéaire mixte (MILP) en présence d'incertitudes sur les coefficientsdes contraintes (à droite et à gauche) lorsque la somme des variations de ces coefficients est bornée. Le problèmerobuste se modélise par un programme en deux étapes, les variables de première étape sont entières ou continues,celles du programme de recours (de deuxième étape) sont continues. Nous montrons que le programme de recours,dans lequel les variables de première étape sont fixées, s'écrit comme un nouveau programme linéairemixte. Le programme robuste se résout ensuite à l?aide d?un algorithme de génération de contraintes. Nous montronsque la méthode s'applique lorsque l?hypothèse de recours complet n?est pas satisfaite et lorsque l?ensembledes incertitudes est un polytope dont les points extrêmes sont connus.

Nous étudions l'optimisation de la conception d?un système hybride possédant des panneaux photovoltaïques,des éoliennes, des batteries et un générateur à diesel. Le comportement du vent et du soleil, ainsi que la demandedes clients, étant aléatoires, nous chercherons une solution robuste permettant de répondre à la demande pourchaque période, tout en minimisant le coût du pire scénario associé au parc choisi. Pour résoudre le problème ro?buste, qui se modélise par un programme en deux étapes, nous étudions un problème dit de recours, et montronsque nous pouvons obtenir une solution optimale de ce problème en temps polynomial grâce à un algorithme deprogrammation dynamique. Nous résolvons alors le problème robuste par une méthode de génération decontraintes.

International audience; Due to the emergence of bandwidth-requiring services, telecommunication operators are being compelled to renew their fix access network, most of them favoring the Fiber To The Home (FTTH) technology. This paper focuses on the optimization of FTTH deployment, which is of prime importance due to the economic stakes. The key design issue here is locating splitters and routing fi bers in an existing network infrastructure to which is associated a graph with given capacities on the edges. No assumption is made on the structure of the graph. First we propose a mixed integer formulation for this decision problem. Then, valid inequalities and problem size reduction schemes are presented. Finally efficiency of solving approaches is assessed through extensive numerical tests performed on Orange real-life data

L'objectif actuel des opérateurs télécoms est de proposer et fournir des services à valeur ajoutée, toujours plus consommateurs en ressources réseaux. Longtemps situé dans le réseau dit " cœur ", le goulot d'étrangle- ment en termes de capacité s'est aujourd'hui dé- placé vers le réseau dit d'" accès ". En ce qui concerne le ré- seau d'accès fixe, cette nécessaire montée en dé- bit s'est effectuée sans changer l'infrastructure phy- sique cuivre, profitant d'une " simple " modula- tion de la fréquence des signaux transportés (bas- débit versus haut-débit). Mais aujourd'hui, le ré- seau cuivre montre ses limites à accompagner la bande passante toujours plus importante attendue par les utilisateurs. Et cette limite ne ferait que s'accentuer dans le futur. Face à ce constat, les opérateurs télécoms sont contraints d'engager un renouvellement de leur ré- seau d'accès fixe. La technologie fibre retenue par France-Télécom Orange est la Fiber To The Home (FTTH), et plus précisément l'architecture Passive Optical Network (PON). Il s'agit d'une archi- tecture dite Point à Multipoints, où chaque fibre optique partant du cœur de réseau est démultipliée lors de son passage dans des équipements passifs ap- pelés coupleurs optiques : une fibre dessert jusqu'à 64 clients qui ont, en bas de chez eux, une fibre optique individuelle. Ce renouvellement complet de l'infrastructure du réseau d'accès fixe s'effectue de manière progres- sive et nécessitera un investissement échelonné es- timé à plusieurs dizaines de milliards d'euros d'ici sa fin prévue en 2020. Face à de tels enjeux financiers et à une telle complexité dans le choix du déploiement d'un réseau FTTH, un outil d'optimisation du design des réseaux FTTH PON apparaissait donc crucial.

Due to the recent increase in bandwidth requirements, telecommunication operators have to support it with the deployment of optical fiber networks through Fiber-To-The-Home Gigabit Passive Optical Network technology (FTTH GPON). One great challenge, in a deregulated context, is to design this network while not knowing who and where the future subscribers will be.We focus on the problem of the robust optical fiber network deployment under demand uncertainty. A two-stage robust optimization model is proposed for this problem, as well as two robust solution methods extending classical results from Ben-Tal et al. and Babonneau et al. in order to be compliant with our uncertainty set.

A general formulation of the problems we are going to consider may be sketched as follows: we are given a system S which is operated by an actor A; this actor tries to choose among several optimal actions which may be represented by subsets of S.An opponent O wants to prevent actor A from operating S in an optimum way by destroying some part P of S. O may in particular wish to find a part P of S as small as possible whose removal will reduce the efficiency of the operation of the system S by a given amount. Another way for O would be to determine a smallest possible part P (the most vital elements) which hits in a sufficient amount every possible optimal action of A.This kind of problem occurs in various situation related to safety or reliability or even in game theoretic contexts.Such problems have been studied from a theoretical point of view in very special cases for which combinatorial optimization models may give an acceptable represen- tation of S. It leads to challenging optimization problems; the goal of this chapter is to give a partial survey of such situations while focusing on simple models based on graphs and other (hopefully tractable) combinatorial structures.

We are concerned with matchings and stable sets in bipartite graphs

Une version complétée a été publiée dans la revue internationale Discrete mathematics en 2009.; International audience; Présentation des concepts de bloqueurs et transversaux pour les couplages maximaux.

International audience

International audience

International audience

International audience

Discrete tomography deals with the reconstruction of discrete homogenous objects from their projections. The reader is referred to the book of Hermann and Kuba [2] for an overview on discrete tomography. The image reconstruction problem is important since its solution is required for developing efficient procedures in image processing, data bases, crystallography, statistics, data compressing,... It can be formulated as follows: given a rectangular array where entries represent the pixels of a digitalized image coloured with k different colors, we consider the problem of reconstructing an image from the number of occurrences of each colour in every column and in every row. The problem is known to be polynomial for k=1, NP-complete for k=3 [1] and its complexity is still open for k=2.Here, we shall consider a graph colouring problem which generalizes both the well known basic graph colouring problem and the above image reconstruction problem. We are given a graph G=(V,E) and a collection P of p subsets Pi of vertices of G. We are also given a set of colours 1, 2, ..,k as well as a collection of p vectors h(Pi) of integers. The problem is to find a k-partition, i.e. a k-colouring, of V such that the number of vertices of Pi coloured with colour j is equal to the jth entry of the vector h(Pi), for all j=1,..,k and all i=1,..,p. The basic graph colouring problem deals with different colour assigned to adjacent vertices: we will call this a "proper" k-colouring otherwise we will call this simply a k-colouring. In this talk, we will consider colouring as well as proper colouring.Let us consider the special case where the graph G is a grid graph, the vertices, denoted by Xrs, are located on row r and column s, r=1,..,m and s=1,..,n, and P is the collection of the m+n chains corresponding to the rows and columns: the problem of finding a k-colouring of G corresponds exactly to the image reconstruction problem. In this talk we will consider some extensions by taking more general classes of graphs such as trees or bipartite graphs. We will restrict our attention to the case where each Pi is a chain in G.We call "cover index" of P, c(P), the maximum number of members of P which may cover a single element of V, i.e. which have a non empty intersection. We call "nested" a family P such that, for any pair of subsets, either one subset is included in the other or they are disjoint; then, the "nesticity" of P, nest(P), is the smallest number of nested families in a partition of P into nested families. First we will give several basic conditions for a solution to exist. Then, we will classify the problems according to the number of colours, the values of c(P) and nest(P), the class of the graph, the diameter of the graph, and so on. For each problem, either we will propose a polynomial time algorithm or we will give complexity results. For instance, we will prove that when G is a tree, the 2-colouring problem and the proper 3-colouring problems are NP-complete even if the maximum degree of G is bounded by 3; but we will propose a polynomial time algorithm solving the k-colouring problem when G is a tree and when any two Pi intersect in at most one vertex. All our results will be summarized in a table.M. Chrobak and C. Dürr (2001), Reconstructing polyatomic stuctures from X-rays: NP-completness proof for three Atoms, Theorical Computer Science, 259(1) 81-98.A. Kuba and G.T. Hermann (1999), Discrete Tomography: Foudations, Algorithms and Applications, Birkhäuser.

International audience

International audience; Le placement de tâches dans la conception et l'utilisation d'une architecture distribuée. Une application à EDF