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.

Given a table with a minimal set of input columns that functionally determines an output column, we introduce a method that tries to gradually decompose the corresponding minimal functional dependency (mfd) to acquire a formula expressing the output column in terms of the input columns. A first key element of the method is to create sub-problems that are easier to solve than the original formula acquisition problem, either because it learns formulae with fewer inputs parameters, or as it focuses on formulae of a particular class, such as Boolean formulae; as a result, the acquired formulae can mix different learning biases such as polynomials, conditionals or Boolean expressions. A second key feature of the method is that it can be applied recursively to find formulae that combine polynomial, conditional or Boolean sub-terms in a nested manner. The method was tested on data for eight families of combinatorial objects; new conjectures were found that were previously unattainable. The method often creates conjectures that combine several formulae into one with a limited number of automatically found Boolean terms.

International audience

With the generalization of cloud infrastructures usage, energy consumption has become a major issue. Scheduling heuristics have been proposed to optimize the resource usage of data center so as to take down the energy consumption. This paper tackles the problem with a different approach by taking into consideration the availability of renewable energy. First we formalize the green energy aware scheduling problem (GEASP) and propose a global model based on constraint programming as well as a search heuristic to solve it efficiently. The proposed model integrates the various aspects inherent to the dynamic planning in a data center: heterogeneous physical machines, various application types (i.e., active or online applications and batch applications), actions and energetic costs of turning ON/OFF physical machines, interrupting/resuming batch applications, CPU and RAM resource consumption, tasks migration, migration costs, and integration of green energy availability. The model can therefore reduce both the costs related to energy consumption and the carbon footprint of a data center. We evaluate the model against the state-of-the-art framework PIKA on real-world workload and solar power traces.

Cloud computing allows for elasticity as users can dynamically benefit from new virtual resources when their workload increases. Such a feature requires highly reactive resource provisioning mechanisms. In this paper, we propose two new workload prediction models, based on constraint programming and neural networks, that can be used for dynamic resource provisioning in Cloud environments. We also present two workload trace generators that can help to extend an experimental dataset in order to test more widely resource optimization heuristics. Our models are validated using real traces from a small Cloud provider. Both approaches are shown to be complimentary as neural networks give better prediction results, while constraint programming is more suitable for trace generation.

Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. This led to general modelling techniques and generic propagators, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for at-most and at-least regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be increased by transitions. We also show that the satisfaction of exact regular counting constraints is NP-hard and that an incomplete propagator for exact regular counting constraints is faster and provides more pruning than the existing propagator from (Beldiceanu, Carlsson, and Petit 2004). Finally, by avoiding the unrolling of the cDFA used by COSTREGULAR, the space complexity reduces from O(n · |Σ| · |Q|) to O(n · (|Σ| + |Q|)), where Σ is the alphabet and Q the state set of the cDFA.

We provide a filtering algorithm achieving GAC for the conjunction of constraints atleast (b, [x(0),x(1),...,x(n-1)], V) and (a(0)*x(0) +...+ a(n-1)*x(n-1)) <= c, where the atleast constraint enforcesb variables out of x(0), x(1), ..., x(n-1) to be assigned to avalue in the set V. This work was motivated by learning simplepolynomials, i.e. finding the coefficients of polynomialsin several variables from example parameter and function values.We additionally require that coefficients be integers, andthat most coefficients be assigned to zero or integers close to0. These problems occur in the context of learning constraintmodels from sample solutions of different sizes. Experimentswith this more global filtering show an improvement by severalorders of magnitude compared to handling the constraintsin isolation or with cost gcc, while also out-performing a0/1 MIP model of the problem.