4 présentations

• 
  15h30 - 15h55

  Column Generation Algorithm for Modularity Density Maximization

  • Sylvain Perron, prés., GERAD, HEC Montréal
  • Gilles Caporossi, GERAD, HEC Montréal

  Many approaches have been proposed in the last decades for finding communities in Network. Although modularity maximization is still the most popular way for finding communities in network, modularity density maximization is known to be an effective alternative to overcome the resolution limit issue of modularity. In this talk, we propose an exact solution method based on column generation for modularity density maximization. We present numerical experiments on real-world networks showing that our algorithm is effective and able to find the exact solution for larger networks than the results reported in the literature so far.

• 
  15h55 - 16h20

  3D Phase Unwrapping for MRI Imagery

  • El Mehdi Oudaoud, prés., Polytechnique Montreal - CIRRELT
  • Youssouf Emine, Polytechnique Montreal - CIRRELT
  • Vidal Thibaut, Massachusetts Institute of Technology, USA

  3D Phase Unwrapping is a pivotal step in analyzing MRI imagery, where traditional methods are often of a heuristic nature and suboptimal outcomes. Central to this challenge is the phenomenon of phase values wrapped between 0 and 2π, which can veil true phase differences and introduce inaccuracies, particularly in critical applications like medical imaging and materials science.

  Our study introduces a novel approach that constructs a graph linking neighboring residues, enabling the rapid detection of "Singular Loops" by the use of the "Graph Untangling" method — surpassing the efficiency of existing state-of-the-art methods. We address these loops by identifying their minimal surfaces, and that by solving a discrete version of the "Plateau Problem". This involves the use of Integer Programming with constraint separation to compute these minimal surfaces, aiming to optimize the unwrapping process.

  Subsequently, we reconstruct the original phase while strategically avoiding these Singular Loops, thereby bypassing the identified optimal minimal surfaces. This methodology not only enhances the accuracy of phase reconstruction but also contributes to a deeper understanding of the complexities involved in 3D Phase Unwrapping. Our findings offer a significant advancement in the field, hopefully transforming practices in medical imaging analysis and beyond.

• 
  16h20 - 16h45

  Modelling service planning with constraint programming

  • Gabriela Sánchez-Yepez, prés., Universidad Autónoma de Nuevo León
  • M. Angélica Salazar-Aguilar, Universidad Autónoma de Nuevo León
  • Vincent Boyer, Universidad Autónoma de Nuevo León

  The telecommunications service planning problem arises from a real-life situation faced by a Mexican telecommunications company. It consists of daily allocating service orders to a set of available crews by ensuring balanced wages. Therefore, it requires finding the optimal assignments and schedules to perform the service orders, including limitations such as the workers' skills and the duration of the working day.
  In this talk, we will describe a constraint programming model as an alternative approach to formulate the problem. We will discuss its performance after conducting extensive experiments over a large set of instances with diverse characteristics. Finally, we will compare the results with those obtained by a mixed-integer linear programming model previously analyzed.

• 
  16h45 - 17h10

  A generic parallel algorithm for community detection in networks based on VNS

  • Gilles Caporossi, prés., GERAD, HEC Montréal
  • Eglantine Camby, Collège Rosemont
  • Sylvain Perron, GERAD, HEC Montréal

  For the last decades, community detection, also called clustering, is a well-studied problem because it has applications in various fields. Variable Neighborhood Search (VNS) has been applied to community detection in networks. If parallel algorithms exist for finding communities in networks and parallel implementations of VNS are designed for a variety of problems, parallel VNS was not yet used for community detection. The results show that parallelizing the variable neighborhood descent increases the performance of the algorithm. We also show that running multiple VNS schemes at the same time also increases the performance. The proposed algorithm can be used to find communities in network regardless of the considered criterion. To illustrate that property, we tested our algorithm on classical instances for modularity maximization as well as for modularity density maximization.