4 Presentations

• 
  03:30 PM - 03:55 PM

  Getting to 1,000x: Solving Large Set-Covering Problems

  • Bruno De Backer, presenter, Google
  • Thibaut Cuvelier, Google

  This talk presents a novel framework for tackling large-scale set-covering problems, enabling the seamless integration and evaluation of diverse solution approaches. Using principles from traditional algorithms, Constraint Programming, and Operations Research, we introduce two distinct algorithms: one for greedy initial solution generation and another for improvement via efficient local search.

  We rigorously compare the performance of our algorithms against established classical implementations. Our results demonstrate a significant leap in scalability, showcasing the ability to find a solution for a set-covering problem with 1 billion subsets in approximately 7 seconds on a single core of an AMD 3995WX processor.

  Furthermore, we explore the impact of these algorithms within a Large Neighborhood Search (LNS) context, demonstrating their remarkable efficiency in this setting. This work offers practical insights and a powerful toolkit for addressing real-world, large-scale optimization challenges.

• 
  03:55 PM - 04:20 PM

  Approaches to solve the Extended Fixed Route Hybrid electric Aircraft Charging Problem with variable vehicle speed

  • Anthony Deschênes, presenter, Université Laval
  • Raphaël Boudreault, Thales
  • Jonathan Gaudreault, Université Laval
  • Claude-Guy Quimper, Université Laval

  Air mobility is rapidly transitioning towards hybrid electric aircraft. In the context of multi-flight missions, aircraft operators will need to consider numerous infrastructure and operational constraints in their planning, where predicting energy usage is critical. This problem is introduced in the previous work as the Extended Fixed Route Hybrid Electric Aircraft Charging Problem (FRHACP) and Dynamic Programming and Mixed Integer Programming approaches are proposed. It consists of deciding a cost-optimal charging, refueling and hybridization strategy for a given aircraft route. In this presentation, we introduce a variant of this problem where variable aircraft speed is considered. We then propose a two-stage Mixed-Integer Programming and genetic programming approaches to solve it and compare its performance on a benchmark of 10 realistic instances. Results demonstrate that considering the variable aircraft speed yield on average to reduction in total costs between 270$ to 550$ in comparison with a Mixed Integer Programming model where variable vehicle speed is not considered.

• 
  04:20 PM - 04:45 PM

  Optimizing Card Grouping for Banking Card Personalization

  • Raphaël Boudreault, presenter, Thales
  • Imadeddine Aziez, Thales

  Thales’ banking card personalization industry requires production orders for individual cards to be grouped into batches. These groupings are based on shared characteristics such as color, personalization technology, packaging, and sending location. They must also follow strict capacity constraints. Additionally, industry-specific requirements introduce further complexity, making it challenging to improve production efficiency. This study presents a Mixed-Integer Programming (MIP) approach to optimize the grouping of individual card requests into efficient production batches. The proposed model employs a weighted objective function to balance multiple priorities, ensuring flexibility and adaptability to diverse operational needs. It also incorporates symmetry-breaking constraints to accelerate solution times. Computational tests using historical data show that the MIP approach significantly outperforms the existing method, which relies on static, predefined grouping rules. The optimized grouping is expected to yield considerable cost savings and operational improvements.

• 
  04:45 PM - 05:10 PM

  Network Topology Optimization for High-Level Information Fusion

  • Imadeddine Aziez, presenter, Thales
  • Raphaël Boudreault, Thales

  The increasing number of sensors in situational awareness contexts poses challenges in achieving timely, actionable, and consistent insights. To prevent information overload, data from heterogeneous sensors—such as radars and cameras—can be fused efficiently. Edge computing enables local processing near sensors, impacting the fusion process by enhancing its efficiency and scalability. However, decentralized networks with diverse processing nodes capabilities introduce an optimization challenge with respect to resource allocation under computational and communication constraints. We propose a Mixed-Integer Programming approach to decide efficient fusion network topology. This involves selecting communication flows and allocating fusion algorithms to processing nodes while meeting network constraints and user requirements. Using a weighted objective function, the model balances multiple priorities. We test the model using realistic instances inspired by a real-life application. Additionally, we conduct a scalability study to evaluate the model's capacity in solving theoretical instances with a larger size of the network. This method has been integrated in a decentralized fusion stack developed by Thales.