Claude-Guy Quimper

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 2024 Journal Article

Corrigendum to “Learning constraints through partial queries” [Artificial Intelligence 319 (2023) 103896]

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

AIJ Journal 2023 Journal Article

Learning constraints through partial queries

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

AAAI Conference 2022 Conference Paper

The SoftCumulative Constraint with Quadratic Penalty

• Yanick Ouellet
• Claude-Guy Quimper

The CUMULATIVE constraint greatly contributes to the success of constraint programming at solving scheduling problems. SOFTCUMULATIVE, a version of the CUMULATIVE constraint where overloading the resource incurs a penalty is, however, less studied. We introduce a checker and a filtering algorithm for SOFTCUMULATIVE, which are inspired by the energetic reasoning rule for the CUMULATIVE. Both algorithms can be used with a classic linear penalty function, but also with a quadratic penalty function, where the penalty of overloading the resource increases quadratically with the amount of the overload. We show that these algorithms are more general than existing algorithms and outperform a decomposition of SOFTCUMULATIVE in practice.

IJCAI Conference 2021 Conference Paper

Improved CP-Based Lagrangian Relaxation Approach with an Application to the TSP

• Raphaël Boudreault
• Claude-Guy Quimper

CP-based Lagrangian relaxation (CP-LR) is an efficient optimization technique that combines cost-based filtering with Lagrangian relaxation in a constraint programming context. The state-of-the-art filtering algorithms for the WeightedCircuit constraint that encodes the traveling salesman problem (TSP) are based on this approach. In this paper, we propose an improved CP-LR approach that locally modifies the Lagrangian multipliers in order to increase the number of filtered values. We also introduce two new algorithms based on the latter to filter WeightedCircuit. The experimental results on TSP instances show that our algorithms allow significant gains on the resolution time and the size of the search space when compared to the state-of-the-art implementation.

IJCAI Conference 2020 Conference Paper

Learning Optimal Decision Trees using Constraint Programming (Extended Abstract)

• Hélène Verhaeghe
• Siegfried Nijssen
• Gilles Pesant
• Claude-Guy Quimper
• Pierre Schaus

Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms have their disadvantages: it is difficult to limit the size of the decision trees while maintaining a good classification accuracy, and it is hard to impose additional constraints on the models that are learned. For these reasons, there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees using constraint programming. Compared to earlier approaches, we show that our approach obtains better performance, while still being sufficiently flexible to allow for the inclusion of constraints. Our approach builds on three key building blocks: (1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize global constraint proposed recently for the problem of itemset mining. This allows our constraint programming approach to deal in a much more efficient way with the decompositions in the learning problem.

IJCAI Conference 2020 Conference Paper

Learning Sensitivity of RCPSP by Analyzing the Search Process

• Marc-André Ménard
• Claude-Guy Quimper
• Jonathan Gaudreault

Solving the problem is an important part of optimization. An equally important part is the analysis of the solution where several questions can arise. For a scheduling problem, is it possible to obtain a better solution by increasing the capacity of a resource? What happens to the objective value if we start a specific task earlier? Answering such questions is important to provide explanations and increase the acceptability of a solution. A lot of research has been done on sensitivity analysis, but few techniques can be applied to constraint programming. We present a new method for sensitivity analysis applied to constraint programming. It collects information, during the search, about the propagation of the CUMULATIVE constraint, the filtering of the variables, and the solution returned by the solver. Using machine learning algorithms, we predict if increasing/decreasing the capacity of the cumulative resource allows a better solution. We also predict the impact on the objective value of forcing a task to finish earlier. We experimentally validate our method with the RCPSP problem.

SoCS Conference 2020 Conference Paper

Solving Classical AI Planning Problems Using Planning-Independent CP Modeling and Search

• Behrouz Babaki
• Gilles Pesant
• Claude-Guy Quimper

The combinatorial problems that constraint programming typically solves belong to the class of NP-hard problems. The AI planning community focuses on even harder problems: for example, classical planning is PSPACE-hard. A natural and well-known constraint programming approach to classical planning solves a succession of fixed plan-length problems, but with limited success. We revisit this approach in light of recent progress on general-purpose branching heuristics. We conduct an empirical comparison of our proposal against state-of-the-art planners.

AAAI Conference 2017 Conference Paper

What’s Hot at CPAIOR (Extended Abstract)

• Claude-Guy Quimper

The 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016), was held in Banff, Canada, May 29 - June 1, 2016. In order to trigger exchanges between the constraint programming and the operations research community, CPAIOR was co-located with CORS 2016, the Canadian Operational Research society's conference.

IJCAI Conference 2016 Conference Paper

Generalizing the Edge-Finder Rule for the Cumulative Constraint

• Vincent Gingras
• Claude-Guy Quimper

We present two novel filtering algorithms for the Cumulative constraint based on a new energetic relaxation. We introduce a generalization of the Overload Check and Edge-Finder rules based on a function computing the earliest completion time for a set of tasks. Depending on the relaxation used to compute this function, one obtains different levels of filtering. We present two algorithms that enforce these rules. The algorithms utilize a novel data structure that we call Profile and that encodes the resource utilization over time. Experiments show that these algorithms are competitive with the state-of-the-art algorithms, by doing a greater filtering and having a faster runtime.

AAAI Conference 2014 Conference Paper

Linear-Time Filtering Algorithms for the Disjunctive Constraint

• Hamed Fahimi
• Claude-Guy Quimper

We present three new filtering algorithms for the DISJUNCTIVE constraint that all have a linear running time complexity in the number of tasks. The first algorithm filters the tasks according to the rules of the time tabling. The second algorithm performs an overload check that could also be used for the CUMULATIVE constraint. The third algorithm enforces the rules of detectable precedences. The two last algorithms use a new data structure that we introduce and that we call the time line. This data structure provides many constant time operations that were previously implemented in logarithmic time by the Θ-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases.

IROS Conference 2013 Conference Paper

A hybrid algorithm for coverage path planning with imperfect sensors

• Michael Morin
• Irène Abi-Zeid
• Yvan R. Petillot
• Claude-Guy Quimper

We are interested in the coverage path planning problem with imperfect sensors, within the context of robotics for mine countermeasures. In the studied problem, an autonomous underwater vehicle (AUV) equipped with sonar surveys the bottom of the ocean searching for mines. We use a cellular decomposition to represent the ocean floor by a grid of uniform square cells. The robot scans a fixed number of cells sideways with a varying probability of detection as a function of distance and of seabed type. The goal is to plan a path that achieves the minimal required coverage in each cell while minimizing the total traveled distance and the total number of turns. We propose an off-line hybrid algorithm based on dynamic programming and on a traveling salesman problem reduction. We present experimental results and show that our algorithm's performance is superior to published results in terms of path quality and computational time, which makes it possible to implement the algorithm in an AUV.

IJCAI Conference 2013 Conference Paper

Constraint Acquisition via Partial Queries

• Christian Bessiere
• Remi Coletta
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks.

AAAI Conference 2012 Conference Paper

Filtering Algorithms Based on the Word-RAM Model

• Philippe Van Kessel
• Claude-Guy Quimper

The Word-RAM is a model of computation that takes into account the capacity of a computer to manipulate a word of w bits with a single instruction. Many modern constraint solvers use a bitset data structure to encode the values contained in the variable domains. Using the algorithmic techniques developed for the Word-RAM, we propose new filtering algorithms that can prune Opwq values from a domain in a single instruction. Experiments show that on a processor with w “ 64, the new filtering algorithms that enforce domain consistency on the constraints A ` B “ C, |A B| “ C and ALL-DIFFERENT can offer a speed up of a factor 10.

IJCAI Conference 2011 Conference Paper

The Multi-Inter-Distance Constraint

• Pierre Ouellet
• Claude-Guy Quimper

We introduce the MULTI-INTER-DISTANCE constraint that ensures no more than m variables are assigned to values lying in a window of p consecutive values. This constraint is useful for modeling scheduling problems where tasks of processing time p compete for m identical resources. We present a propagator that achieves bounds consistency in cubic time. Experiments show that this new constraint offers a much stronger filtering than an edge-finder and that it allows to solve larger instances of the runway scheduling problem.

AAAI Conference 2010 Conference Paper

Propagating Conjunctions of AllDifferent Constraints

• Christian Bessiere
• George Katsirelos
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We study propagation algorithms for the conjunction of two ALLDIFFERENT constraints. Solutions of an ALLDIFFERENT constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite matchings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two ALLDIFFERENT constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.

IJCAI Conference 2009 Conference Paper

• Christian Bessiere
• George Katsirelos
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We show that some common and important global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing of variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.

AAAI Conference 2008 Conference Paper

Decompositions of Grammar Constraints

• Claude-Guy Quimper

A wide range of constraints can be compactly specified using automata or formal languages. In a sequence of recent papers, we have shown that an effective means to reason with such specifications is to decompose them into primitive constraints (Quimper & Walsh 2006; 2007). We can then, for instance, use state of the art SAT solvers and profit from their advanced features like fast unit propagation, clause learning, and conflict-based search heuristics. This approach holds promise for solving combinatorial problems in scheduling, rostering, and configuration, as well as problems in more diverse areas like bioinformatics, software testing and natural language processing. In addition, decomposition may be an effective method to propagate other global constraints.

AAAI Conference 2008 Conference Paper

The Parameterized Complexity of Global Constraints

• Christian Bessiere
• Brahim Hnich
• Claude-Guy Quimper

We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have natural parameters which make them fixedparameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation.

AAAI Conference 2006 Conference Paper

A Quadratic Propagator for the Inter-Distance Constraint

• Claude-Guy Quimper

We present a new propagator achieving bound consistency for the INTER-DISTANCE constraint. This constraint ensures that, among a set of variables X1, .. ., Xn, the difference between two variables is at least p. This restriction models, in particular, scheduling problems in which tasks require p contiguous units of a resource to be completed. Until now, the best known propagator for bound consistency had time complexity O(n3 ). In this work we propose a quadratic propagator for the same level of consistency. We then show that this theoretical gain gives savings of an order of magnitude in our benchmark of scheduling problems.

IJCAI Conference 2003 Conference Paper

A Fast and Simple Algorithm for Bounds Consistency of the All Different Constraint

• Alejandro Ldpez-Ortiz
• Claude-Guy Quimper
• John Tromp
• Peter van Beek

In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms—on problems with an easily identifiable property—state-ofthe-art commercial implementations of propagators for stronger forms of local consistency.