We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in O(n + ~m) time, where ~m is the sum, for each vertex v, of the minimum between the numbers of successors and non-successors of v. Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases, outperforming a GPU-accelerated version. In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.

The Kunming-Montreal Global Biodiversity Framework aims to protect 30% of terrestrial, inland water, marine, and coastal ecosystems worldwide, and ensuring that at least 30% of these areas are under effective restoration by 2030. Maintaining and restoring ecological connectivity between natural habitats and protected areas is a key feature of this target. Achieving it will require effective and inclusive spatial planning supported by appropriate decision-support tools. Most spatial planning models address budget as an objective and connectivity as a constraint, formulating problems with Steiner trees. In many real-world cases, such as landscape-scale restoration planning, this formulation is inappropriate when environmental managers seek to optimise connectivity under a budget constraint. This problem was previously addressed with Constraint Programming (CP) and graph variables, but the current approach is severely limited in terms of spatial resolution. In this article, we formalise this problem as the budget-constrained graph connectivity optimisation problem. Based on a real case study: the restoration of forest connectivity in New Caledonia, we illustrate why ``naive'' CP approaches are inefficient. In response, we provide a preprocessing method based on Hanan grids which preserves the existence of at least one optimal solution. Finally, we assess the efficiency of our approach in the New Caledonian case study.

In the context of Edge Computing or Cyber-Physical Systems, cross-functional, and cross-geographical DevOps teams are in charge of automating deployments, configuration, and management (i.e., reconfiguration) of complex, large-scale, highly dynamic, and geo-distributed service-oriented software systems. In this context, DevOps teams cannot reasonably manually coordinate their reconfiguration operations in a global manner. Furthermore, as disconnection is the norm in these paradigms, a central entity responsible for reconfiguration should be avoided, and the set of changes to apply should be as fast as possible. This paper presents Ballet, a fast tool to automate decentralized choreographies (i.e., coordination) of cross-DevOps reconfiguration. We show a gain of 42.6% for a deployment scenario and 24% for an update scenario on an OpenStack case study.

International audience

Fog Computing is a paradigm aiming to decentralize the Cloud by geographically distributing away computation, storage and network resources as well as related services. This notably reduces bottlenecks and data movement. However, managing Fog resources is a major challenge because the targeted systems are large, geographically distributed, unreliable and very dynamic. Cloud systems are generally managed via centralized autonomic controllers automatically optimizing both application QoS and resource usage. To leverage the self-management of Fog resources, we propose to orchestrate a fleet of autonomic controllers in a decentralized manner, each with a local view of its own resources. In this paper, we present our SeMaFoR (Self-Management of Fog Resources) vision that aims at collaboratively operating Fog resources. SeMaFoR is a generic approach made of three cornerstones: an Architecture Description Language for the Fog, a collaborative and consensual decision-making process, and an automatic coordination mechanism for reconfiguration.

Constraint programming provides generic techniques to efficiently solve combinatorial problems. In this paper, we tackle the natural question of using constraint solvers to sample combinatorial problems in a generic way. We propose an algorithm, inspired from Meel’s ApproxMC algorithm on SAT, to add hashing constraints to a CP model in order to split the search space into small cells of solutions. By sampling the solutions in the restricted search space, we can randomly generate solutions without revamping the model of the problem. We ensure the randomness by introducing a new family of hashing constraints: randomly generated tables. We implemented this solving method using the constraint solver Choco-solver. The quality of the randomness and the running time of our approach are experimentally compared to a random branching strategy. We show that our approach improves the randomness while being in the same order of magnitude in terms of running time.

By relying on small sized and massively distributed infrastructures, the Edge computing paradigm aims at supporting the low latency and high bandwidth requirements of the next generation services that will leverage IoT devices (e.g., video cameras, sensors). To favor the advent of this paradigm, management services, similar to the ones that made the success of Cloud computing platforms, should be proposed. However, they should be designed in order to cope with the limited capabilities of the resources that are located at the edge. In that sense, they should mitigate as much as possible their footprint. Among the different management services that need to be revisited, we investigate in this paper the monitoring one. Monitoring functions tend to become compute-, storage- and network-intensive, in particular because they will be used by a large part of applications that rely on real-time data. To reduce as much as possible the footprint of the whole monitoring service, we propose to mutualize identical processing functions among different tenants while ensuring their quality-of-service (QoS) expectations. We formalize our approach as a constraint satisfaction problem and show through micro-benchmarks its relevance to mitigate compute and network footprints.

Providing efficient black-box search procedures is one of the major concerns for constraint-programming solvers. Most of the contributions in that area follow the fail-first principle, which is very useful to close the search tree or to solve SAT/UNSAT problems. However, for real- life applications with an optimization criterion, proving optimality is often unrealistic. Instead, it is very important to compute a good solution fast. This paper introduces a value selector heuristic focusing on objective bounds to make the first solution good. Experiments show that it improves former approaches on a wide range of problems.