4 présentations

• 
  10h30 - 10h55

  Optimizing the Quadratic Knapsack Problem with Binary Decision Diagrams: A Bound Tightening Approach

  • M. Eliass Fennich, prés., Université Laval
  • Leandro C. Coelho, Université Laval
  • Franklin Djeumou Fomeni, GERAD, Polytechnique Montréal

  Binary Decision Diagrams (BDDs) have emerged as a novel approach in combinatorial optimization over the past decade. They offer a solution to any binary optimization problem with a dynamic programming formulation. Leveraging two efficient state-of-the-art compiling approaches, BDDs can provide bounds for these problems. Combined with a previously introduced BDD branch and bound approach, these problems can be solved exactly. This is advantageous because, unlike classical branch and bound that rely on linear programs, BDDs offer a flexible framework for nonlinear problems.
  While BDD-based approaches outperform linear program-based methods, they lack the dual bound tightening feature crucial for evaluating solution quality—a strength of classical branch and bound. To address this limitation, we propose integrating dual bound tightening into BDD-based branch and bound, enhancing its effectiveness. Experimental validation, primarily conducted on the Quadratic Knapsack Problem (QKP), demonstrates the competitiveness of our approach. By challenging the established dominance of a cut and branch algorithm, particularly excelling on the category of hidden clique instances, our proposed BDD compiling approach showcases its potential. Our results achieve parity or surpass the state of the art on other various QKP instances, highlighting the efficacy of our dual bound tightening integration into BDD-based branch and bound.

• 
  10h55 - 11h20

  A hybrid dynamic programming and local search algorithm for coverage path planning with imperfect extended detection

  • Dominik Richard, prés., Université Laval
  • Michael Morin, Assistant Professor at the Department of Operations and Decision Systems, Université Laval, Québec, Canada
  • Claude-Guy Quimper, Université Laval

  Underwater minesweeping operations optimization using autonomous underwater vehicles (AUV) requires the application of multi-objective optimization algorithms for coverage path planning (CPP). Focusing on the case of a REMUS 100 AUV equipped with a sidescan sonar, we address the CPP problem with an imperfect extended detection (CPPIED). An efficient solution for a REMUS 100 AUV, characterized by the ability to cover long distances with infrequent turns at a constant speed and altitude, minimizes both the path length and the number of turns (in that order). To our knowledge, the current state of the art for the CPPIED is a heuristic called Dynamic programming Sweeper (DpSweeper). Operating under the assumption that the CPPIED can be reduced to the Generalized Covering Salesman Problem (GCSP), we propose to adapt the LS2 local search heuristic to the CPPIED. We show that our algorithm improve the efficiency of the solutions provided by DpSweeper on a benchmark of instances of various sizes.

• 
  11h20 - 11h45

  A parallel variable neighborhood search for alpha-neighbor facility location problems

  • Guilherme O. Chagas, prés., Université Laval, CIRRELT
  • Luiz Antonio Nogueira Lorena, Instituto Nacional de Pesquisas Espaciais
  • Rafael D. C. dos Santos, Instituto Nacional de Pesquisas Espaciais
  • Jacques Renaud, Université Laval, CIRRELT
  • Leandro C. Coelho, Université Laval

  In this work, we employ the less is more approach to develop a Parallel Variable Neighborhood Search (VNS) algorithm for the alpha-neighbor p-center problem (alpha-NpCP) and the alpha-neighbor p-median problem (alpha-NpMP). In the alpha-neighbor problems, one seeks to open p facilities and assign each of the n customers to their closest alpha ones. The objective is to minimize the maximum distance of a customer to its alpha-th facility, in the case of the alpha-NpCP, and the sum of the distances from each customer to their alpha nearest facilities, in the case of the alpha-NpMP. Our VNS adapts simple but efficient algorithms and data structures from literature to the alpha-NpCP and alpha-NpMP context. Several experimental tests show that our VNS outperforms more complex state-of-the-art algorithms. Regarding the alpha-NpCP, on 120 instances, our algorithm improved best-known solutions for 22, with an average improvement of 34.26%. Moreover, on 231 instances derived from the TSPLIB set, we improved the solutions for 115, with an average improvement of 5.30%. Considering the alpha-NpMP results, our heuristic obtained better results than a heuristic from literature in all 80 instances tested, finding optimal solutions in all these instances.

• 
  11h45 - 12h10

  An exact bidirectional pulse algorithm for the constrained shortest path

  • Nicolas Cabrera, prés., HEC Montreal
  • Andres Medaglia, Universidad de los Andes
  • Leonardo Lozano, University of Cincinnati

  A constrained shortest path is a minimum-cost sequence of arcs on a directed network that satisfies knapsack-type constraints on the resource consumption over the arcs. We propose an exact method based on a recursive depth-first search procedure known as the pulse algorithm (PA). One of the key contributions of the proposal lies in a bidirectional search strategy leveraged on parallelism. In addition, we developed a pulse-based heuristic that quickly finds near-optimal solutions and shows great potential for column generation (CG) schemes. We present computational experiments over large real-road networks with up to 6 million nodes and 15 million arcs. We illustrate the use of the bidirectional PA in a CG scheme to solve a multi-activity shift scheduling problem, where the pricing problem is modeled as a constrained-shortest path with multiple resource constraints.