ABSTRACT The purpose of this work is to develop an algorithmic optimization approach for a capacitated multi‐commodity flow problem, where the objective is to minimize the total link costs, where the cost of each arc increases convexly with its utilization. This objective is particularly relevant in telecommunication networks, where device performance can deteriorate significantly as the available bandwidth on a link becomes limited. By optimizing this convex function, traffic is efficiently distributed across the network, ensuring optimal use of available resources and preserving capacity for future demands. This paper describes the convex multi‐commodity flow problem and presents methodologies to solve both its Splittable and Unsplittable variants. In the Splittable version, flows can be fractionally distributed across multiple paths, while in the Unsplittable version, each commodity must be routed through a single path. Our approach employs Column‐Generation techniques to address the convexly increasing cost functions associated with arc utilization, effectively accommodating various forms of convex increasing cost functions, including non‐differentiable or black‐box convex increasing functions. The proposed methods demonstrate strong computational efficiency, offering a robust framework for managing network flows in complex telecommunication environments.

Virtual Network Embedding (VNE) is an optimization problem at the core of many modern network telecommunication technologies related to the implementation of virtual networks, such as Network Slicing. The VNE problem consists in finding an optimal assignment of virtual demands to physical resources, encompassing simultaneous placement and routing decisions.We study the offline version of the VNE, which arises in the context of decision-making for resource allocation and network slice planning. For large networks, the heuristics of the literature often struggle to find solutions, especially when available resources (on nodes and edges) are sparse.To address these challenges, we explore mathematical programming approaches. Since the classical Flow Formulation provides a weak linear relaxation, we consider a novel formulation, based on a partition of the virtual graph into smaller virtual subgraphs. Since this formulation has an exponential number of variable, its linear relaxation can be solved with Column Generation. We devise a Price-Branch heuristic able to solve large instances, while providing optimality gap. The resulting computational experiments indicate our Price-Branch heuristic is often the only algorithm able to find a solution from a certain instance size, largely outperforming the Flow Formulation or literature heuristics.

The Optimal Power Flow (OPF) problem is a central optimization problem in power systems. Its global resolution is a challenge since it is highly nonconvex and NP-hard. Semidefinite Programming (SDP) is a powerful tool to progress towards global optimality as semidefinite relaxations provide tight lower bounds for the OPF problem. However, solving semidefinite relaxations for large power networks is very costly, because it is required to exploit its sparsity for achieving this aim. One efficient way to exploit sparsity for the OPF problem is to use clique decomposition techniques along with state-of-the-art interior point algorithms. Yet many clique decompositions can be computed for the same sparse SDP problem, their performance can significantly varies in practice. In this context, it is crucial to identify a good decomposition, where by good we mean a decomposition that allows to solve the SDP relaxation of the OPF problem in a small amount of time. At the moment, it is not possible in the literature to find a systematic analysis that allows to characterize in detail the properties of a good decomposition, the works proposed so fare relies on the basic assumption that there is a trade-off between the size and the number of the cliques: a decomposition with only one large clique is problematic because of memory issues but a decomposition with many tiny cliques is not advisable either as it implies lots of linking constraints, which slows down the resolution. In this work, we propose to use machine learning techniques to understand what are the characteristics of a good clique decomposition. More precisely, we propose to identify the relevant features to describe a good clique decomposition, using both classification and regression approaches. The results show that the decomposition identified with the proposed techniques are comparable with the state of the art.

In this paper, we investigate the use of a swarm of drones as mobile data gathering sinks for scattered wireless sensors over large areas. Precisely, we address the path planning issue with the objective of minimizing the drones' travel duration. Several criteria are also considered, such as: 1) energy autonomy of the drones, 2) a good fairness regarding route lengths, 3) collision avoidance and 4) drones' tracking enabled by the transmission of their positions to terrestrial base stations. These base stations, and consequently the drones' paths, must be carefully determined in the aim to statistically guarantee a minimum threshold on the delivery ratio of drones' position packets. The problem is formalized as a multiple Traveling Salesman problem, which is known to be NP-Hard. To cope with the computational complexity that rises for realistic parameters, we propose a heuristic approach based on a column generation approach.

International audience

The market of drones is expected to grow significantly by the near few years, while military, civil and commercial applications continue to emerge. In an earlier study we focused on the path planning problem for a swarm of UAVs for data gathering mission with the objective to minimize the travel duration with respect to the energy autonomy, a better fairness regarding tours and finally avoiding collisions among the drones of the same swarm. In this paper, we address the tracking and the data gathering issue and thus we evaluate both the received tracking and gathering packets rate under different conditions of speed and interference.

A general task in data mining consists in finding all rectangles of 1 in a boolean matrix in which the order of the rows and columns is not important. However, most algorithms which have been developed to solve this task are unable to be adapted to real data that may contain noise. The effect of the noise is to shatter relevant item sets into a set of small irrelevant item sets, yielding an explosion in the number of resulting item sets. Recent algorithms that have been proposed to address this problem suffer from various limitations such as the large number of results, the execution time which remains very high and the inability to discover overlapping patterns. In this work, we propose a new heuristic approach based on a graph algorithm for the efficient extraction of item set patterns in noisy binary contexts. This method is based on maximal flow/minimal cut algorithms to find dense sub graphs of 1 in the graph associated to the boolean data matrix. To evaluate our approach, various experiments have been performed on both synthetic data and real datasets from bioinformatic applications. We have compared our results on various synthetic datasets and a gene-expression data with various methods and demonstrate that i) our method is quite efficient ii) the patterns extracted by our algorithm have a better quality than the other methods.

In few years, graph cuts have become a leading method for solving a wide range of problems in computer vision. However, graph cuts involve the construction of huge graphs which sometimes do not fit in memory. Currently, most of the max-flow algorithms are impracticable to solve such large scale problems. In the image segmentation context, some authors have proposed heuristics [1, 2, 3, 4] to get round this problem. In this paper, we introduce a new strategy for reducing exactly graphs. During the creation of the graph, before creating a new node, we test if the node is really useful to the max-flow computation. The nodes of the reduced graph are typically located in a narrow band surrounding the object edges. Empirically, solutions obtained on the reduced graphs are identical to the solutions on the complete graphs. A parameter of the algorithm can be tuned to obtain smaller graphs when an exact solution is not needed. The test is quickly computed and the time required by the test is often compensated by the time that would be needed to create the removed nodes and the additional time required by the computation of the cut on the larger graph. As a consequence, we sometimes even save time on small scale problems.