Nicolas Beldiceanu

IJCAI Conference 2025 Conference Paper

Bimodal Depth-First Search for Scalable GAC for AllDifferent

• Sulian Le Bozec-Chiffoleau
• Nicolas Beldiceanu
• Charles Prud'homme
• Gilles Simonin
• Xavier Lorca

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.

IJCAI Conference 2025 Conference Paper

Towards the 30 by 30 Kunming-Montreal Global Biodiversity Framework Target: Optimising Graph Connectivity in Constraint-Based Spatial Planning

• Sulian Le Bozec-Chiffoleau
• Dimitri Justeau-Allaire
• Xavier Lorca
• Charles Prud'homme
• Gilles Simonin
• Philippe Vismara
• Philippe Birnbaum
• Nicolas Rinck

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.

AAAI Conference 2024 Conference Paper

Composing Biases by Using CP to Decompose Minimal Functional Dependencies for Acquiring Complex Formulae

• Ramiz Gindullin
• Nicolas Beldiceanu
• Jovial Cheukam-Ngouonou
• Rémi Douence
• Claude-Guy Quimper

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.

AIJ Journal 2016 Journal Article

A parametric propagator for pairs of Sum constraints with a discrete convexity property

• Jean-Noël Monette
• Nicolas Beldiceanu
• Pierre Flener
• Justin Pearson

AAAI Conference 2014 Conference Paper

Propagating Regular Counting Constraints

• Nicolas Beldiceanu
• Pierre Flener
• Justin Pearson
• Pascal Van Hentenryck

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.

SoCS Conference 2013 Conference Paper

GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials

• Naina Razakarison
• Mats Carlsson
• Nicolas Beldiceanu
• Helmut Simonis

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.

ECAI Conference 2012 Conference Paper

An O(nlog n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization

• Nicolas Beldiceanu
• Mats Carlsson
• Thierry Petit
• Jean-Charles Régin

This paper gives an O&lpar; nlog&thinsp; n&rpar; bound-consistency filtering algorithm for the conjunction alldifferent&lpar; V0, V1, &mldr; ,Vn&minus; 1&rpar; &and; f&lpar; V0&rpar; &target; f&lpar; V1&rpar; &target; &mldr; &target; f&lpar; Vn&minus; 1&rpar; &le; cst, &lpar; V0, V1, &mldr; ,Vn&minus; 1, cst&isin; +&rpar; , where (, &target;) is a commutative group, f is a unary function, and both &target; and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

IJCAI Conference 2011 Conference Paper

A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

• Thierry Petit
• Nicolas Beldiceanu
• Xavier Lorca

This paper introduces the Seqbin meta-constraint with a polytime algorithm achieving generalized arc-consistency. Seqbin can be used for encoding counting constraints such as Change, Smooth, or InncreasingNValue. For all of them the time and space complexity is linear in the sum of domain sizes, which improves or equals the best known results of the literature.

ICAPS Conference 2008 Conference Paper

Filtering for a Continuous Multi-Resources cumulative Constraint with Resource Consumption and Production

• Emmanuel Poder
• Nicolas Beldiceanu

Within the framework of continuous and multi-resources cumulative constraints, a task T expresses a piecewise linear resource function and is represented by a sequence of p contiguous trapezoid sub-tasks with variable durations and heights. In this context, this paper provides an algorithm in O(p) for filtering the resource assignment and the temporal attributes of such a task, according to a trapezoid of a minimum cumulated resource profile, in order to avoid an overflow of the resource capacity.