Personne :
Quimper, Claude-Guy

Photo de profil
Adresse électronique
Date de naissance
Projets de recherche
Structures organisationnelles
Fonction
Nom de famille
Quimper
Prénom
Claude-Guy
Affiliation
Université Laval. Département d'informatique et de génie logiciel
ISNI
ORCID
Identifiant Canadiana
ncf10572729
person.page.name

Filtres

2014 - 201942020 - 20221
5
5
Réinitialiser les filtres

Paramètres

Résultats de recherche

Voici les éléments 1 - 5 sur 5
  • Publication
    Accès libre
    Learning the parameters of global constraints using branch-and-bound
    (Springer Link, 2017-08-23) Sweeney, Jason Pierre; Picard-Cantin, Émilie; Bouchard, Mathieu; Quimper, Claude-Guy
    Precise constraint satisfaction modeling requires specific knowledge acquired from multiple past cases. We address this issue with a general branch-and-bound algorithm that learns the parameters of a given global constraint from a small set of positive solutions. The idea is to cleverly explore the possible combinations taken by the constraint’s parameters without explicitly enumerating all combinations. We apply our method to learn parameters of global constraints used in timetabling problems such as Sequence and SubsetFocus. The later constraint is our adaptation of the constraint Focus to timetabling problems.
  • Publication
    Accès libre
    Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last
    (Kluwer, 2018-04-11) Ouellet, Yanick; Fahimi, Hamed; Quimper, Claude-Guy
    We present new filtering algorithms for Disjunctive and Cumulative constraints, each of which improves the complexity of the state-of-theart algorithms by a factor of log n. We show how to perform TimeTabling and Detectable Precedences in linear time on the Disjunctive constraint. Furthermore, we present a linear-time Overload Checking for the Disjunctive and Cumulative constraints. Finally, we show how the rule of Not-first/Not-last can be enforced in quadratic time for the Cumulative constraint. These algorithms rely on the union find data structure, from which we take advantage to introduce a new data structure that we call it time line. This data structure provides 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. We also show that the time line can be used to solve specific scheduling problems.
  • Publication
    Accès libre
    Learning parameters for the sequence constraint from solutions
    (SpringerLink, 2016-08-23) Sweeney, Jason Pierre; Picard-Cantin, Émilie; Bouchard, Mathieu; Quimper, Claude-Guy
    This paper studies the problem of learning parameters for global constraints such as Sequence from a small set of positive examples. The proposed technique computes the probability of observing a given constraint in a random solution. This probability is used to select the more likely constraint in a list of candidates. The learning method can be applied to both soft and hard constraints
  • Publication
    Accès libre
    The balance constraint family
    (Springer, 2014-09-08) Bessière, Christian; Picard-Cantin, Émilie; Hebrard, Emmanuel; Quimper, Claude-Guy; Katsirelos, George; Kiziltan, Zeynep; Walsh, Toby
    The BALANCE constraint introduced by Beldiceanu ensures solutions are balanced. This is useful when, for example, there is a requirement for solutions to be fair. BALANCE bounds the difference B between the minimum and maximum number of occurrences of the values assigned to the variables. We show that achieving domain consistency on BALANCE is NP-hard. We therefore introduce a variant, ALLBALANCE with a similar semantics that is only polynomial to propagate. We consider various forms of ALLBALANCE and focus on ATMOSTALLBALANCE which achieves what is usually the main goal, namely constraining the upper bound on B. We provide a specialized propagation algorithm, and a powerful decomposition both of which run in low polynomial time. Experimental results demonstrate the promise of these new filtering methods.
  • Publication
    Restriction temporaire
    Ant colony optimization for path planning in search and rescue operations
    (Elsevier, 2022-06-12) Morin, Michael; Abi-Zeid, Irène; Quimper, Claude-Guy
    In search and rescue operations, an efficient search path, colloquially understood as a path maximizing the probability of finding survivors, is more than a path planning problem. Maximizing the objective adequately, i.e., quickly enough and with sufficient realism, can have substantial positive impact in terms of human lives saved. In this paper, we address the problem of efficiently optimizing search paths in the context of the NP-hard optimal search path problem with visibility, based on search theory. To that end, we evaluate and develop ant colony optimization algorithm variants where the goal is to maximize the probability of finding a moving search object with Markovian motion, given a finite time horizon and finite resources (scans) to allocate to visible regions. Our empirical results, based on evaluating 96 variants of the metaheuristic with standard components tailored to the problem and using realistic size search environments, provide valuable insights regarding the best algorithm configurations. Furthermore, our best variants compare favorably, especially on the larger and more realistic instances, with a standard greedy heuristic and a state-of-the-art mixed-integer linear program solver. With this research, we add to the empirical body of evidence on an ant colony optimization algorithms configuration and applications, and pave the way to the implementation of search path optimization in operational decision support systems for search and rescue.