4 présentations

• 
  15h30 - 15h55

  Analyzing shake strategies for the CMMSA

  • Marcos Robles, prés., Universidad Rey Juan Carlos
  • Sergio Cavero, Universidad Rey Juan Carlos
  • Eduardo G. Pardo, Universidad Rey Juan Carlos

  The Cyclic Min-Max Sitting Arrangement problem (CMMSA) is a graph layout optimization problem where vertices of an input signed graph must be embedded on a cyclic host graph. The input graph contains weighted edges, either +1 or -1, representing positive and negative relationships between vertices. For each vertex, a penalty occurs when vertices connected by negative edges are positioned closer than those connected by positive edges. The goal is to minimize the maximum number of such penalties occurring at any single vertex. By focusing on minimizing the maximum penalties, the CMMSA ensures a more balanced distribution of conflicts compared to the classical Cyclic Minimum Sitting Arrangement problem, which minimizes the sum of penalties across all vertices. This paper presents a comprehensive study based on Variable Neighborhood Search (VNS) methodologies for solving the CMMSA. Building upon successful applications of VNS in related problems, we analyze multiple algorithmic variants and strategies. Specifically, our investigation focuses on two main components: a Variable Neighborhood Descent (VND) scheme that combines two specialized local search procedures, and a Basic VNS (BVNS) framework incorporating five distinct shake procedures. We evaluate these approaches using established benchmark instances from the literature. Our computational experiments demonstrate the effectiveness of the proposed VNS methods in solving the CMMSA and provide insights into which combinations of components yield the best results for different instance characteristics. The findings not only highlight the efficacy of the proposed approach but also provide a foundation for future research on the CMMSA and related graph layout optimization problems.

• 
  15h55 - 16h20

  A variable neighborhood search heuristic for semi-supervised minimum sum-of-squares clustering

  • Mahuton Hugues Midingoyi, prés., Polytechnique Montréal
  • André Meneses , Universidade Federal do Rio Grande do Norte
  • Daniel Aloise, Polytechnique Montréal

  Semi-supervised clustering is an unsupervised learning model that incorporates prior information to enhance the learning process. Among various clustering objectives, the minimum sum-of-squares clustering (MSSC) is widely used to partition data by minimizing intra-cluster variances. In our work, we propose a Variable Neighborhood Search (VNS) heuristic for MSSC, where prior information is given in the form of pairwise must-link and cannot-link constraints.
  Our approach relies on the efficient evaluation of data points reassignments among the clusters after the model reformulation. Computational experiments indicate that, in most cases, our proposed VNS heuristic outperforms the solutions produced by the state-of-the-art heuristic algorithms within a similar computational time.

• 
  16h20 - 16h45

  A Variable Neighborhood Search Heuristic for the Electric Dial-A-Ride Problem

  • Mohammad Karimi, prés., Polytechnique Montréal - CIRRELT
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal

  This paper addresses the Electric Dial-A-Ride Problem, which involves scheduling a fleet of electric vehicles (EVs) to provide ride-sharing services for customers with specified origins and destinations. The problem incorporates several key features: (1) the use of EVs and consideration of partial charging strategies, (2) a concave piecewise linear charging function, (3) time-dependent charging pricing policies, (4) multiple types of charging infrastructure, and (5) capacity constraints for charging stations. To solve this problem, we propose a variable neighborhood search heuristic with various neighborhood classes, combined with a mixed-integer programming technique to optimize the fleet’s charging strategy. The performance of the proposed algorithm is evaluated using large and very large datasets, including instances with up to 10,000 requests adapted from the literature and real-world data. The results demonstrate that the algorithm delivers highly competitive solutions compared to existing approaches in the literature.

• 
  16h45 - 17h10

  Parallel Variable Neighborhood Search: A Thematic Survey

  • Tatjana Davidovic, prés., Mathematical Institute of the Serbian Academy of Sciences and Arts, Belgrade, Serbia

  The main focus of this study is on the survey of parallelization strategies for the Variable Neighborhood Search (VNS) metaheuristic. Parallelization is a widely-used tool for increasing the efficiency of many algorithms. For deterministic algorithms, the main goal is to speed up the execution of all required computations by distributing them among the available processing units. When stochastic algorithms (like metaheuristics) are considered, the expectations are increased: by engaging multiple processing units, one can hope to improve the quality of the resulting solution, if possible, within the reduced running time. However, usually this is not easy to achieve. Various aspects of parallel computing should be examined, such as identification of parallelizable parts, distribution granularity, balancing the computational effort of various processing units, synchronizing their work, optimizing communication (data exchange) delays, etc. In addition, the compatibility between the available hardware resources and the required computational requirements should also be taken into account. Last, but not least, characteristics of the optimization problem in hand and it's suitability for parallel and distributed treatment should not be neglected. Parallel metaheuristic is actually a completely new algorithm that may significantly differ from the original, sequential variant. In some cases, this property may be preferable, however, in many others the authors are trying to preserve the good characteristics of the original algorithm. This survey analyses the existing results related to the parallelization of VNS considering all mentioned aspects. We try to derive some useful recommendations how to address various optimization problems taking into account the available multiprocessor architecture and the existing sequential VNS implementations. The study is co-authored by Teodor Gabriel Crainic, UQAM and CIRRELT and Tatjana Jakšić-Krüger, MI-SASA.

  Keywords: metaheuristics, parallel computing, synchronization, communication, cooperation