4 Presentations

• 
  03:30 PM - 03:55 PM

  A Variable Neighborhood Search heuristic applied to the minmax response time sequencing problem

  • João Henrique Pereira, Universidade Federal da Paraíba
  • Bruno Jefferson de Sousa, Universidade Federal da Paraíba
  • Caroline Rocha, Ivado Labs
  • Daniel Aloise, presenter, Polytechnique Montréal

  The mRTP (Minmax Response Time Problem) is a fair sequencing problem that arises whenever tasks, clients, products, or events need to be ordered in a way that minimizes the variability of the expected time between successive allocations of scarce resources. With applications ranging from medical shift scheduling to industrial machine maintenance, the mRTP has not been as extensively explored in the literature compared to other fair sequencing problems. This paper proposes specialized data structures for mRTP, which, combined with a novel algorithm based on the VNS metaheuristic, yields the best solutions for the reference instance set in the literature to date.

• 
  03:55 PM - 04:20 PM

  Improved Multi-Objective Variable Neighborhood Search procedure for the optimization of software modularity

  • Javier Yuste Moure, presenter, Universidad Rey Juan Carlos
  • Eduardo G. Pardo, Universidad Rey Juan Carlos
  • Manuel López-Ibáñez, Alliance Manchester Business School, University of Manchester

  Title

  Improved Multi-Objective Variable Neighborhood Search procedure for the optimization of software modularity

  Authors

  Javier Yuste, Eduardo G. Pardo, Manuel López-Ibáñez

  Problem statement and context

  The Software Module Clustering Problem (SMCP) is an optimization problem aimed at enhancing software modularity, a crucial aspect of code maintainability. In 2024, an algorithm based on the Multi-Objective Variable Neighborhood Search (MO-VNS) scheme was developed for the SMCP, addressing a variant of the problem with five different objectives. However, the study identified some weaknesses in the MO-VNS scheme.

  Key innovations

  This work proposes some improvements to the MO-VNS procedure to address previously identified weaknesses. Specifically, it focuses on the Multi-Objective Variable Neighborhood Descent (MO-VND) scheme. The proposed alternative enhances the anytime behavior of the classic MO-VND scheme by (i) uniformly distributing efforts across different objectives and (ii) exploring different acceptance criteria during the search process.

  Methodological approach

  Fourteen instances were randomly selected from a widely studied SMCP dataset. To ensure fairness, all methods were coded by the same programmer using the same programming language and optimization framework and executed on the same computing server. Moreover, they started from the same initial solution (built by a random constructive heuristic) for each instance. The proposed methods were run with a maximum computing time of fifteen minutes. To evaluate the behavior of the methods under comparison, one hundred snapshots of the solutions found were taken at different times. The results were evaluated using quality indicators recommended by the literature: Hypervolume (HV), Modified Inverted Generational Distance (IGD+) and the number of non-dominated solutions found (PFS).

  Main results/contributions

  The proposed variant obtains better solutions on average than the classic scheme at any moment during the execution time according to every quality indicator evaluated: HV, IGD+, and PFS.

• 
  04:20 PM - 04:45 PM

  Exact methods and a variable neighborhood search for the robust capacitated p-median problem

  • Rafael Ajudarte de Campos, presenter, Department of Operations and Decision Systems, Université Laval
  • Guilherme O. Chagas, Université Laval, CIRRELT
  • Leandro C. Coelho, Université Laval
  • Pedro Munari, Department of Production Engineering, Federal University of São Carlos, Brazil

  The capacitated p-median problem (CPMP) involves placing p identical facilities in a network and assigning customer nodes to these facilities to satisfy all customer demands with minimal transportation costs. In practical applications, demand and distance parameters are often uncertain during the planning process, leading to infeasible or excessively costly solutions if these uncertainties are disregarded. This paper addresses the robust CPMP (RCPMP), which incorporates demand uncertainty into the problem using the robust optimization paradigm. We propose a general framework to model and solve the RCPMP, considering different polyhedral uncertainty sets, namely the cardinality-constrained and the knapsack sets. We develop exact approaches encompassing compact models, different families of valid inequalities, and branch-and-cut and branch-and-price algorithms, exploring both implemented uncertainty sets and problem structure. Furthermore, we implement an efficient Variable Neighborhood Search (VNS) heuristic to solve these robust variants, which incorporates state-of-the-art algorithms, parallelization techniques, and optimized data structures. Computational experiments using adapted benchmark instances with up to 400 nodes indicate the effectiveness of the proposed approaches. The results show that using parallelization and hash tables within the VNS heuristic promotes significant performance improvements and yields near-optimal solutions for most instances, as well as outperforming the exact approaches in several instances where the optimal solution was not found. Moreover, these results highlight the benefits of using robust solutions in practical settings, especially when considering different uncertainty sets to generate solutions with advantageous trade-offs between cost and risk.

• 
  04:45 PM - 05:10 PM

  The Importance of Being Interpretable: Generative AI capabilities and Metaheuristic Research

  • Aidan Riordan, presenter, College of Charleston, Charleston, South Carolina, USA
  • Xavier Hansen,
  • Daniel Aloise, École Polytechnique de Montréal, Montreal, Canada
  • Raúl Martín, Universidad Rey Juan Carlos, Madrid, Spain

  Building on our seminal exploration of the topic, we present an updated assessment of the evolving relationship between Generative AI and metaheuristics, emphasizing recent advancements in large language models (LLMs) and their implications for optimization research. Over the past year, LLMs have demonstrated remarkable progress in handling unstructured data and performing complex tasks associated with reasoning, emphasizing the importance of interpretability in both AI and metaheuristics. We first review key breakthroughs in LLM capabilities relevant to optimization, including programming, mathematical problem-solving, and scientific knowledge representation. Next, we showcase practical applications of Generative AI in metaheuristic research, such as automated code generation (demonstrating the creation of local search code with comparable execution time and solution quality), literature reviews, and the design of neighborhood structures for Variable Neighborhood Search. Finally, we examine the growing field of LLM interpretability research and discuss how principles from interpretable metaheuristics might contribute valuable insights to understanding these increasingly complex AI systems.