Author name cluster

Gilles Simonin

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.

10 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

IJCAI Conference 2024 Conference Paper

Polynomial Time Presolve Algorithms for Rotation-Based Models Solving the Robust Stable Matching Problem

Sulian Le Bozec-Chiffoleau
Charles Prud'homme
Gilles Simonin

The Robust Stable Matching (RSM) problem involves finding a stable matching that allows getting another stable matching within a minimum number of changes when a pair becomes forbidden. It has been shown that such a problem is NP-Hard. In this paper, we enrich the mathematical model for the RSM problem based on new theoretical properties. We derive from these properties new polynomial time pre-solving algorithms which both reduce the search space and speed up the exploration. We also extend our results to the instances of the Many-to-Many problem and give its corresponding constraint programming (CP) model. We show how the use of our algorithms improve the state-of-the-art results and make it possible to obtain proofs of optimality on large instances via the CP model.

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

TCS Journal 2019 Journal Article

Complexity Study for the Robust Stable Marriage Problem

Begum Genc
Mohamed Siala
Gilles Simonin
Barry O'Sullivan

The Robust Stable Marriage problem (RSM) is a variant of the classic Stable Marriage problem in which the robustness of a given stable matching is measured by the number of modifications required to find an alternative stable matching should some pairings break due to an unforeseen event. We focus on the complexity of finding an ( a, b ) -supermatch. An ( a, b ) -supermatch is defined as a stable matching in which if any a (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those a men/women and the partners of at most b others. We first discuss a model based on independent sets for finding ( 1, 1 ) -supermatches. Secondly, in order to show that deciding whether or not there exists a ( 1, b ) -supermatch is NP -complete, we first introduce a SAT formulation for which the decision problem is NP -complete by using Schaefer's Dichotomy Theorem. We then show the equivalence between this SAT formulation and finding a ( 1, 1 ) -supermatch on a specific family of instances. We also focus on studying the threshold between the cases in P and NP -complete for this problem.

Details DOI

IJCAI Conference 2017 Conference Paper

Finding Robust Solutions to Stable Marriage

Begum Genc
Mohamed Siala
Barry O'Sullivan
Gilles Simonin

We study the notion of robustness in stable matching problems. We first define robustness by introducing (a, b)-supermatches. An (a, b)-supermatch is a stable matching in which if a pairs break up it is possible to find another stable matching by changing the partners of those a pairs and at most b other pairs. In this context, we define the most robust stable matching as a (1, b)-supermatch where b is minimum. We show that checking whether a given stable matching is a (1, b)-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.

PDF Details

AAAI Conference 2017 Short Paper

Robust Stable Marriage

Begum Genc
Mohamed Siala
Barry O'Sullivan
Gilles Simonin

Stable Marriage (SM) is a well-known matching problem, where the aim is to match a set of men and women. The resulting matching must satisfy two properties: there is no unassigned person and there are no other assignments where two people of opposite gender prefer each other to their current assignments. We propose a new version of SM called as Robust Stable Marriage (RSM) by combining stability and robustness. We deﬁne robustness by introducing (a, b)-supermatches, which has been inspired by (a, b)supermodels (Ginsberg, Parkes, and Roy 1998). An (a, b)supermatch is a stable matching, where if at most a pairs want to break up, it is possible to ﬁnd another stable matching by breaking at most b other pairs.

PDF Details

AAAI Conference 2016 Conference Paper

A CP-Based Approach for Popular Matching

Danuta Chisca
Mohamed Siala
Gilles Simonin
Barry O'Sullivan

We propose a constraint programming approach to the popular matching problem. We show that one can use the Global Cardinality Constraint to encode the problem even in cases that involve ties in the ordinal preferences of the applicants.

PDF Details

ECAI Conference 2014 Conference Paper

Optimisation for the Ride-Sharing Problem: a Complexity-based Approach

Gilles Simonin
Barry O'Sullivan

The dial-a-ride problem is a classic challenge in transportation and continues to be relevant across a large spectrum of applications, e. g. door-to-door transportation services, patient transportation, etc. Recently a new variant of the dial-a-ride problem, called ride-sharing, has received attention due to emergence of the use of smartphone-based applications that support location-aware transportation services. The general dial-a-ride problem involves complex constraints on a time-dependent network. In ride-sharing riders (resp. drivers) specify transportation requests (resp. offers) between journey origins and destinations. The two sets of participants, namely riders and drivers, have different constraints; the riders have time windows for starting and finishing the journey, while drivers have a starting time window, a destination, and a vehicle capacity. The challenge is to maximise the overall utility of the participants in the system which can be defined in a variety of ways. In this paper we study variations of the ride-sharing problem, under different notions of utility, from a computational complexity perspective, and identify a number of tractable and intractable cases. These results provide a basis for the development of efficient methods and heuristics for solving problems of real-world scale.

Details

ICAPS Conference 2011 Conference Paper

Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph

Gilles Simonin
Rodolphe Giroudeau
Jean-Claude König
Benoît Darties

This paper presents a generalization of the coupled-task scheduling problem introduced by Shapiro, where considered tasks are subject to incompatibility constraint depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the border between P and NP-completeness when some other input parameters are restricted (e. g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of the complexity of scheduling problems with coupled-task given by Orman and Potts to our problem, determine new complexity results, and thus propose a new visualization including incompatibility constraint. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.

Details