Author name cluster

Xavier Lorca

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

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.

PDF Details DOI

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.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources

Arthur Godet
Xavier Lorca
Emmanuel Hebrard
Gilles Simonin

In this paper, we consider the Parallel Machine Scheduling Problem with Additional Unit Resources, which consists in scheduling a set of n jobs on m parallel unrelated machines and subject to exactly one of r unit resources. This problem arises from the download of acquisitions from satellites to ground stations. We ﬁrst introduce two baseline constraint models for this problem. Then, we build on an approximation algorithm for this problem, and we discuss about the efﬁciency of designing an improved constraint model based on these approximation results. In particular, we introduce new constraints that restrict search to executions of the approximation algorithm. Finally, we report experimental data demonstrating that this model signiﬁcantly outperforms the two reference models.

PDF Details

JAIR Journal 2019 Journal Article

Revisiting Counting Solutions for the Global Cardinality Constraint

Giovanni Lo Bianco
Xavier Lorca
Charlotte Truchet
Gilles Pesant

Counting solutions for a combinatorial problem has been identified as an important concern within the Artificial Intelligence field. It is indeed very helpful when exploring the structure of the solution space. In this context, this paper revisits the computation process to count solutions for the global cardinality constraint in the context of counting-based search. It first highlights an error and then presents a way to correct the upper bound on the number of solutions for this constraint.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Systematic Conservation Planning for Sustainable Land-use Policies: A Constrained Partitioning Approach to Reserve Selection and Design.

Dimitri Justeau-Allaire
Philippe Vismara
Philippe Birnbaum
Xavier Lorca

Faced with natural habitat degradation, fragmentation, and destruction, it is a major challenge for environmental managers to implement sustainable land use policies promoting socioeconomic development and natural habitat conservation in a balanced way. Relying on artificial intelligence and operational research, reserve selection and design models can be of assistance. This paper introduces a partitioning approach based on Constraint Programming (CP) for the reserve selection and design problem, dealing with both coverage and complex spatial constraints. Moreover, it introduces the first CP formulation of the buffer zone constraint, which can be reused to compose more complex spatial constraints. This approach has been evaluated in a real-world dataset addressing the problem of forest fragmentation in New Caledonia, a biodiversity hotspot where managers are gaining interest in integrating these methods into their decisional processes. Through several scenarios, it showed expressiveness, flexibility, and ability to quickly find solutions to complex questions.

PDF Details

ECAI Conference 2014 Conference Paper

Self-decomposable Global Constraints

Jean-Guillaume Fages
Xavier Lorca
Thierry Petit

Scalability becomes more and more critical to decision support technologies. In order to address this issue in Constraint Programming, we introduce the family of self-decomposable constraints. These constraints can be satisfied by applying their own filtering algorithms on variable subsets only. We introduce a generic framework which dynamically decompose propagation, by filtering over variable subsets. Our experiments over the CUMULATIVE constraint illustrate the practical relevance of self-decomposition.

Details

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.

PDF Details DOI