Pour savoir comment effectuer et gérer un dépôt de document, consultez le « Guide abrégé – Dépôt de documents » sur le site Web de la Bibliothèque. Pour toute question, écrivez à corpus@ulaval.ca.
 

Personne :
Quimper, Claude-Guy

En cours de chargement...
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

Résultats de recherche

Voici les éléments 1 - 8 sur 8
  • PublicationAccè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
  • PublicationAccès libre
    Relaxation of the optimal search path problem with the cop and robber game
    (2014-09-01) Simard, Frédéric; Morin, Michael; Quimper, Claude-Guy; Laviolette, François; Desharnais, Josée
    In the Optimal Search Path problem from search theory, the objective is to find a finite length searcher’s path that maximizes the probability of detecting a lost wanderer on a graph. We introduce a novel bound on the probability of finding the wanderer in the remaining search time and discuss how this bound is derived from a relaxation of the problem into a game of cop and robber from graph theory. We demonstrate the efficiency of this bound on a constraint programming model of the problem.
  • PublicationAccè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.
  • PublicationAccès libre
    Decision Support for Search and Rescue Response Planning
    (ISCRAM, 2017-05) Morin, Michael; Abi-Zeid, Irène; Quimper, Claude-Guy; Nilo, Oscar; Comes, Tina; Bénaben, Frédérick; Hanachi, Chihab; Lauras, Matthieu; Montarnal, Aurélie
    Planning, controlling and coordinating search and rescue operations is complex and time is crucial for survivors who must be found quickly. The search planning phase is especially important when the location of the incident is unknown. We propose, implement, solve, and evaluate mathematical models for the multiple rectangular search area problem. The objective is to define optimal or near-optimal feasible search areas for the available search and rescue units that maximize the probability of success. We compare our new model to an existing model on problem instances of realistic size. Our results show that we are able to generate, in a reasonable time, near optimal operationally feasible plans for searches conducted in vast open spaces. In an operational context, this research can increase the chances of finding survivors. Ultimately, as our models get implemented in the Canadian Coast Guard search planning tool, this can translate into more lives being saved.
  • PublicationAccè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.
  • PublicationAccè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.
  • PublicationRestriction 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.
  • PublicationRestriction temporaire
    Learn, compare, search : one sawmill’s search for the best cutting patterns across and/or trees
    (Springer, 2023-10-25) Ménard, Marc-André; Morin, Michael; Khachan, Mohammed; Gaudreault, Jonathan; Quimper, Claude-Guy
    A sawmilling process scans a wood log and must establish a series of cutting and rotating operations to perform in order to obtain the set of lumbers having the most value. The search space can be expressed as an and/or tree. Providing an optimal solution, however, may take too much time. The complete search for all possibilities can take several minutes per log and there is no guarantee that a high-value cut for a log will be encountered early in the process. Furthermore, sawmills usually have several hundred logs to process and the available computing time is limited. We propose to learn the best branching decisions from previous wood logs and define a metric to compare two wood logs in order to branch first on the options that worked well for similar logs. This approach (Learn, Compare, Search, or LCS) can be injected into the search process, whether we use a basic Depth-First Search (DFS) or the state-of-the-art Monte Carlo Tree Search (MCTS). Experiments were carried on by modifying an industrial wood cutting simulator. When computation time is limited to five seconds, LCS reduced the lost value by 47.42% when using DFS and by 17.86% when using MCTS.