International audience

ABSTRACT Machine learning techniques are increasingly used for high‐stakes decision‐making, such as college admissions, loan attribution, or recidivism prediction. Thus, it is crucial to ensure that the models learnt can be audited or understood by human users, do not create or reproduce discrimination or bias and do not leak sensitive information regarding their training data. Indeed, interpretability, fairness, and privacy are key requirements for the development of responsible machine learning, and all three have been studied extensively during the last decade. However, they were mainly considered in isolation, while in practice they interplay with each other, either positively or negatively. In this survey paper, we review the literature on the interactions between these three desiderata. More precisely, for each pairwise interaction, we summarize the identified synergies and tensions. These findings highlight several fundamental theoretical and empirical conflicts, while also demonstrating that jointly considering these different requirements is challenging when one aims at preserving a high level of utility. To solve this issue, we also discuss possible conciliation mechanisms, showing that a careful design can enable to successfully handle these different concerns in practice.

Port automation has emerged as a transformative solution enabling seaport management to efficiently handle the escalating volume of operations, driven in part by the advancements in low-cost long-distance maritime transport. In this context, the use of Automated Guided Vehicles for the loading and unloading of ships creates a need to optimize the conflict-free routing of these vehicles, in order to guarantee the safe transportation of goods within automated container terminals. In this work, we propose an Integer Linear Programming model to address the problem of collision-free path planning of Automated Guided Vehicles in container terminals where each vehicle is associated to one routing request. Numerical experiments are performed to evaluate the proposed method’s performances. Conclusions are drawn regarding its efficiency, and future avenues of research to address the problem are proposed.

The growing interest in explainable artificial intelligence(XAI) for critical decision making motivates the need for interpretable machine learning (ML) models. In fact, due to their structure (especially with small sizes), these models are inherently understandable by humans. Recently, several exact methods for computing such models are proposed to overcome weaknesses of traditional heuristic methods by providing more compact models or better prediction quality. Despite their compressed representation of Boolean functions, Binary decision diagrams (BDDs) did not gain enough interest as other interpretable ML models. In this paper, we first propose SAT-based models for learning optimal BDDs (in terms of the number of features) that classify all input examples. Then, we lift the encoding to a MaxSAT model to learn optimal BDDs in limited depths, that maximize the number of examples correctly classified. Finally, we tackle the fragmentation problem by introducing a method to merge compatible subtrees for the BDDs found via the MaxSAT model. Our empirical study shows clear benefits of the proposed approach in terms of prediction quality and interpretability (i.e., lighter size) compared to the state-of-the-art approaches.

Machine Learning models are increasingly used for decision making, in particular in high-stakes applications such as credit scoring, medicine or recidivism prediction. However, there are growing concerns about these models with respect to their lack of interpretability and the undesirable biases they can generate or reproduce. While the concepts of interpretability and fairness have been extensively studied by the scientific community in recent years, few works have tackled the general multi-class classification problem under fairness constraints, and none of them proposes to generate fair and interpretable models for multi-class classification. In this paper, we use Mixed-Integer Linear Programming (MILP) techniques to produce inherently interpretable scoring systems under sparsity and fairness constraints, for the general multi-class classification setup. Our work generalizes the SLIM (Supersparse Linear Integer Models) framework that was proposed by Rudin and Ustun to learn optimal scoring systems for binary classification. The use of MILP techniques allows for an easy integration of diverse operational constraints (such as, but not restricted to, fairness or sparsity), but also for the building of certifiably optimal models (or sub-optimal models with bounded optimality gap).

FairCORELS is an open-source Python module for building fair rule lists. It is a multi-objective variant of CORELS, a branch-and-bound algorithm to learn certifiably optimal rule lists. FairCORELS supports six statistical fairness metrics, proposes several exploration parameters and leverages on the fairness constraints to prune the search space efficiently. It can easily generate sets of accuracy-fairness trade-offs. The models learnt are interpretable by design and a sparsity parameter can be used to control their length.

Many state-of-the-art methods for combinatorial games rely on Monte Carlo Tree Search (MCTS) method, coupled with machine learning techniques, and these techniques have also recently been applied to combinatorial optimization. In this paper, we propose an efficient approach to a Travelling Salesman Problem with time windows and capacity constraints from the automotive industry. This approach combines the principles of MCTS to balance exploration and exploitation of the search space and a backtracking method to explore promising branches, and to collect relevant information on visited subtrees. This is done simply by replacing the Monte-Carlo rollouts by budget-limited runs of a DFS method. Moreover, the evaluation of the promise of a node in the Monte-Carlo search tree is key, and is a major difference with the case of games. For that purpose, we propose to evaluate a node using the marginal increase of a lower bound of the objective function, weighted with an exponential decay on the depth, in previous simulations. Finally, since the number of Monte-Carlo rollouts and hence the confidence on the evaluation is higher towards the root of the search tree, we propose to adjust the balance exploration/exploitation to the length of the branch. Our experiments show that this method clearly outperforms the best known approaches for this problem.

International audience

Recently, several exact methods to compute decision trees have been introduced. On the one hand, these approaches can find optimal trees for various objective functions including total size, depth or accuracy on the training set and therefore. On the other hand, these methods are not yet widely used in practice and classic heuristics are often still the methods of choice. In this paper we show how the SAT model proposed by [Narodytska et.al 2018] can be lifted to a MaxSAT approach, making it much more practically relevant. In particular, it scales to much larger data sets; the objective function can easily be adapted to take into account combinations of size, depth and accuracy on the training set; and the fine-grained control of the objective function it offers makes it particularly well suited for boosting. Our experiments show promising results. In particular, we show that the prediction quality of our approach often exceeds state of the art heuristics. We also show that the MaxSAT formulation is well adapted for boosting using the well-known AdaBoost Algorithm.

Abstract Free space optical communications are becoming a mature technology to cope with the needs of high data rate payloads for future low‐earth orbiting observation satellites. However, they are strongly impacted by clouds. In this paper, we aim to find a network of optical ground stations maximizing the percentage of data acquired by a low‐earth orbiting satellite that can be transferred to the Earth, taking into consideration cloud information. This problem can be separated in two parts and solved hierarchically: the selection of a network of optical ground stations and the assignment of downloads to visibility windows of the stations. We present theoretical and practical results regarding the complexity of the latter subproblem and propose a dynamic programming algorithm to solve it. We combine this algorithm with two methods for the enumeration of the stations, and compare them with a mixed integer linear program (MILP). Results show that even if the MILP can solve scenarios over small horizons, the hierarchical approaches outperform it in term of computation time while still achieving optimality for larger instances.

Ridesharing, in which drivers offer to share their rides, allows reduction of travel costs for both drivers and riders; such practice is increasingly popular. Modern ridesharing systems, enhanced with location-based features, have improved user experience by enabling drivers and riders to arrange a trip in near real time. However, the fine-grained nature of location data collected by the service providers and exchanged between users raises privacy issues that could disrupt the adoption of such systems. In this paper, we present SRide: a privacy-preserving protocol for ridesharing that addresses the matching problem for dynamic ridesharing systems. We design and implement a prototype of SRide that operates in four steps. First, it generalizes users spatiotemporal data of users. Next, it relies on a secure filtering protocol to compute feasible matches. Then, it uses an improved version of Priv-2SP-SP- a privacy-preserving protocol to compute meeting points for ridesharing- to compute a ridesharing score for each feasible pair. Finally, it computes the optimal assignment of drivers and riders based on their ridesharing scores. We conduct an experimental trace-driven evaluation of the proposed scheme to demonstrate its practical feasibility.

For space industries, free-space optical communications are becoming a mature technology, but the impact of their use to download observations from spatial imagery systems has still to be evaluated. Unlike current radio-frequency technology, freespace optical communications are strongly impacted by weather conditions, and most notably by clouds. In order to cope with the later, it is necessary to achieve ground station diversity, i.e. having a network of optical ground stations able to receive data from satellites. In this paper, we aim to find a subset of a given number of ground stations maximizing the amount of data that can be downloaded from a low-earth orbiting satellite to the Earth during its missions. We present a Mixed Integer Linear Program model and a hierarchical method based on an exhaustive enumeration of the sets of stations and on a dynamic programming algorithm to solve it. The efficiency of this method is evaluated on several instances based on real ground station networks and on cloud cover throughout the last twenty years.

In this work, a multiagent network flow problem is addressed, aiming at characterizing the properties of stable flows and allowing their computation. Two types of agents are considered:transportation‐agents, that carry a flow of products on a given network and another agent, either aproduceror acustomer, who is willing to ship (receive, respectively), products. Every transportation‐agent controls a set of arcs, each having a capacity that can be increased up to a certain point at a given cost. The other agent (i.e., the customer/producer) is interested in maximizing the flow transshipped through the network. To this aim, we assume it offers the transportation‐agents a reward that is proportional to the realized flow value. This particular multiagent framework is referred to as a Multiagent network expansion game. We characterize and find particular stable strategies (i.e., Nash equilibria) that are of interest for this game. We particularly focus on the problem of finding a Nash Equilibrium and a sharing policy that maximize the value of the total flow. We prove that this problem is NP‐hard in the strong sense and show how such a strategy can be characterized considering paths in specific auxiliary graphs. We also provide a mixed integer linear programming formulation to solve the problem. Computational experiments are provided to prove the effectiveness of our approach and derive some insights for practitioners. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 94–109 2017

Network virtualization is seen as a key networking paradigm for building diverse network services and architectures over a shared network infrastructure. Assigning network resources to virtual links and, more generally to virtual network topologies, efficiently and on-demand is one of the most challenging components of any network virtualization solution. This paper addresses the problem of on-line resource allocation of multiple virtual links on a Software Defined Network (SDN) infrastructure. The application context that is targeted is primarily the online provisioning of virtual overlay networks even if it can be broadened to address more general virtual networks. Considering an SDN physical infrastructure allows a complete freedom in choosing the optimal physical paths and the associated resources that support the virtual links with no interference from any other network function (such as routing). However, for the time being, forwarding in an SDN network is resource consuming with a noticeable impact on the size of the flow tables. Hence, forwarding (i.e. switching) resources should be carefully considered by the network resource allocation algorithm. This paper proposes a novel Integer-Linear formulation of the above cited problem by taking into account: (1) point-to-point as well as point-to-multipoint virtual links, each with an associated bandwidth requirement and a maximum transfer delay requirement, (2) two types of network resources, namely network links' bandwidth and nodes' switching resources, and (3) optionally, path splitting which allows a virtual link to be established on multiple physical paths. We report preliminary experimental results on a real network topology in an overloaded scenario (bandwidth requests largely exceed network capacity); they show that our algorithm outperforms shortest path heuristics with a gain on the admission rate (of virtual links requests) that ranges from 5 to 15% (compared to the most efficient heuristic) and with a computation time less than a few seconds.

A Multi-Agent Minimum-Cost Flow problem is addressed in this paper. It can be seen as a basic multi-agent transportation problem where every agent can control the capacities of a set of elementary routes (modeled as arcs inside a network), each agent incurring a cost proportional to the chosen capacity. We assume that a customer is interesting in transshipping a product flow from a source to a sink node through the transportation network. It offers a reward that is proportional to the flow that the agents manage to provide. The reward is shared among the agents according to a pre-established policy. This problem can be seen as a non-cooperative game where every agent aims at maximizing its individual profit. We take interest in finding stable strategies (i.e., Nash Equilibrium) such that no agent has any incentive to modify its behavior. We show how such equilibrium can be characterized by means of augmenting or decreasing path in a reduced network. We also focus on the problem of finding a Nash equilibrium that maximizes the flow value and prove its NP-hardness.

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks. We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.

This paper addresses the Job-Shop scheduling problem with generic time-lags (JSPGTL). This problem is a generalization of the Job-Shop scheduling problem where extra (minimum and maximum) delays can be introduced between any operations. First a state of the art on the job-shop scheduling with time-lags is provided and we outline that the determination of a feasible solution for the JSPGTL is clearly a difficult problem as contrary to more basic time-lags problems. Secondly we propose some dedicated constraint propagation rules witch aim to detect some inconsistancies for the JSPGTL. The efficiency of these rules is illustrated on a small example. These propagation rules can be included in a heuristic method for the acceleration of the search for feasible solution thanks to early detection of certain inconsistancies. This work is the first step of a collaboration which aims to propose a new feature for the resolution of JSPGTL.

This paper addresses the solving of mixed Task Scheduling and Resource Allocation Problems in an integrated way using a backtracking algorithm. Several ordering heuristics are proposed to improve the efficiency of this algorithm. Experiments show the impact of these heuristics on the quality of the first solution obtained. We also compare our integrated approach with a sequential solving of scheduling and allocation problems.