3 Presentations

• 
  02:00 PM - 02:25 PM

  Metaheuristics for Preference-based Constrained Optimization

  • Sina Alizadeh, presenter, University of Regina
  • Sifat E Jahan, University of Regina
  • Malek Mouhoub, University of Regina

  Effective representation and reasoning about constraints together with user preferences play a vital role in various applications such as recommender systems, planning, scheduling, vehicle routing, resource allocation, and configuration. In this context, the Constrained Conditional Preference Network (CCP-net) model has been designed to capture and express both constraints and user conditional preferences. Solving the CCP-net consists in finding a set of Pareto-optimal solutions that meet all constraints while optimizing the qualitative preferences. Finding Pareto solutions in CCP-nets using exact methods like branch and bound can be time-consuming. Alternatively, we can rely on those methods trading the quality of the returned solutions for execution time. We introduce {three} bio-inspired methods to enhance the efficiency of finding Pareto solutions in CCP-nets. Additionally, we experimentally compare these bioinspired techniques with those derived from an exact method, focusing on the quality of returned solutions and the run-time performance. The results of the experiments, conducted on random CCP-net instances, are reported and discussed.

• 
  02:25 PM - 02:50 PM

  Sampling Frequent and Diverse Patterns Through Compression

  • François Camelin, presenter, MT Atlantique, LS2N, UMR CNRS 6004,
  • Samir Loudni, MT Atlantique, LS2N, UMR CNRS 6004
  • Gilles Pesant, Polytechnique Montréal
  • Charlotte Truchet, STMS UMR 9912, Sorbonne Université
  • Gilles Pesant, Polytechnique Montréal

  Exhaustive pattern extraction methods in databases often struggle with
  speed and output control, leading to the generation of numerous redundant pat-
  terns. Sampling-based approaches offer a solution by limiting output size and
  ensuring faster computation. However, these methods can still produce redun-
  dant patterns when a large number is required. For preference learning tasks, it
  is essential to obtain a concise set of diverse and representative patterns. To ad-
  dress this, we propose integrating compression techniques into the sampling pro-
  cess. This integration refines the selection of representative patterns from sampled
  transactions while guiding the sampling toward greater diversity. Our approach
  outperforms existing methods by achieving a more diverse and efficient set of
  output patterns.

• 
  02:50 PM - 03:15 PM

  Full description of the polytope of chemical graphs

  • Alain Hertz, presenter, Polytechnique Montréal and GERAD
  • Sébastien Bonte, Université de Mons
  • Gauvain Devillez, Université de Mons
  • Valentin Dusollier, Université de Mons
  • Hadrien Mélot, Université de Mons
  • David Schindl, Haute École de Gestion de Genève

  We consider chemical graphs that are defined as connected graphs of maximum degree at most 3. These graphs, where vertices represent atoms and edges represent bonds, allow researchers to investigate various chemical and physical properties of molecules through graph-theoretical concepts.
  A topological index, or molecular descriptor, is a graph invariant used to study specific physicochemical properties of molecules. We focus on degree-based topological indices which are computed from the sum of the weights of the edges, each edge having a weight defined by a formula using the degrees of its endpoints.
  Studies have shown that many of these degree-based topological indices have the same extremal properties in the sense that the chemical graphs that maximize or minimize the values of these indices are often the same. We show that this is not surprising because the polytope that defines chemical graphs of any given order and size contains at most 10 facets and at most 16 extremal points, whereas a chemical graph that maximizes or minimizes a given degree-based topological index is necessarily one of these extreme points.