Search

The field of Weakly Supervised Learning (WSL) has recently seen a surge of popularity, with numerous papers addressing different types of "supervision deficiencies", namely: poor quality, non adaptability, and insufficient quantity of labels. Regarding quality, label noise can be of different types, including completely-at-random, at-random or even not-at-random. All these kinds of label noise are addressed separately in the literature, leading to highly specialized approaches. This paper proposes an original, encompassing, view of Weakly Supervised Learning, which results in the design of generic approaches capable of dealing with any kind of label noise. For this purpose, an alternative setting called "Biquality data" is used. It assumes that a small trusted dataset of correctly labeled examples is available, in addition to an untrusted dataset of noisy examples. In this paper, we propose a new reweigthing scheme capable of identifying noncorrupted examples in the untrusted dataset. This allows one to learn classifiers using both datasets. Extensive experiments that simulate several types of label noise and that vary the quality and quantity of untrusted examples, demonstrate that the proposed approach outperforms baselines and state-of-the-art approaches., 8 pages, 7 figures

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.

One of the challenges of cloud computing is to optimally and efficiently assign virtual ma- chines to physical machines. The aim of telecommunication operators is to minimize the map- ping cost while respecting constraints regarding location, assignment and capacity. In this paper we first propose an exact formulation leading to a 0-1 bilinear constrained problem. Then we introduce a variety of linear cuts by exploiting the problem structure and present a Lagrange decomposition based B&B algorithm to obtain optimal solutions efficiently. Numerically, we show that our valid inequalities close over 80% of the optimality gap incurred by the well-known McCormick relaxation, and demonstrate the computational advantage of the proposed B&B algorithm with extensive numerical experiments., submitted for journal publication; copyright preserved

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

We consider linear programs involving uncertain parameters and propose a new tractable robust counterpart which contains and generalizes several other models including the existing Affinely Adjustable Robust Counterpart and the Fully Adjustable Robust Counterpart. It consists in selecting a set of poles whose convex hull contains some projection of the uncertainty set, and computing a recourse strategy for each data scenario as a convex combination of some optimized recourses (one for each pole). We show that the proposed multipolar robust counterpart is tractable and its complexity is controllable. Further, we show that under some mild assumptions, two sequences of upper and lower bounds converge to the optimal value of the fully adjustable robust counterpart. To illustrate the approach, a robust problem related to lobbying under some uncertain opinions of authorities is studied. Several numerical experiments are carried out showing the advantages of the proposed robustness framework and evaluating the benefit of adaptability., 35 pages, 1 figure, 9 tables, submitted journal paper

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.