Personne : Quimper, Claude-Guy
En cours de chargement...
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
8 Résultats
Résultats de recherche
Voici les éléments 1 - 8 sur 8
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-GuyThis 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 constraintsPublication Accè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éeIn 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.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, TobyThe 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 Accè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éliePlanning, 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.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-GuyPrecise 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-GuyWe 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 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-GuyIn 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.Publication Restriction 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-GuyA 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.