4 présentations

• 
  13h00 - 13h22

  Learning for Polynomial Optimization Problems

  • Bissan Ghaddar, prés., Ivey Business School

  The use of machine learning techniques to improve the performance of branch-and-bound optimization algorithms is a very active area in the context of mixed integer linear problems, but little has been done for non-linear optimization. To bridge this gap, we develop a learning framework for spatial branching and show its efficacy in the context of the Reformulation-Linearization Technique for polynomial optimization problems. The proposed learning is performed offline, based on instance-specific features and with no computational overhead when solving new instances. Novel graph-based features are introduced, which turn out to play an important role in the learning. Experiments on different benchmark instances from MINLPLib and QPLIB show that the learning-based branching selection and learning-based constraint generation significantly outperform the standard approaches.

• 
  13h22 - 13h44

  Neural Genetic Operators for Combinatorial Optimization

  • Changhyun Kwon, prés., KAIST

  Genetic algorithms are widely recognized as effective metaheuristics for tackling diverse combinatorial optimization problems. However, their performance heavily depends on the careful design of genetic operators, which requires comprehensive understanding and problem-specific knowledge. This paper introduces a novel automated framework that uses deep learning to design genetic operators, thereby reducing dependency on expert knowledge. The proposed framework interprets crossover as a parent-conditioned generation process, ensuring offspring inherit partial solutions from both parents via masking schemes. Extensive experiments demonstrate that the automated genetic algorithm outperforms deep learning methods with additional searches on routing problems, such as the Traveling Salesman Problem. Moreover, the framework's adaptability is validated through applications to simulation-based combinatorial optimization problems, including hardware design and molecular optimization, where it consistently surpasses existing genetic algorithm methods.

• 
  13h44 - 14h06

  Machine Learning-Enhanced Strategies for the Quadratic Multidimensional Knapsack Problem

  • Richard Forrester, prés., Dickinson College
  • Lucas Waddell, Bucknell University

  The quadratic multidimensional knapsack problem (QMDKP) generalizes both the multidimensional knapsack problem and the quadratic knapsack problem. To address this challenging combinatorial optimization problem, we propose a novel machine learning-driven framework. A logistic regression model predicts the inclusion probability of each item in the knapsack, forming the basis for a greedy heuristic that efficiently explores the solution space. This heuristic is further enhanced by integration with a genetic algorithm that leverages the probabilistic insights from the machine learning model. Computational results demonstrate the effectiveness of this integrated framework.

• 
  14h06 - 14h28

  A Policy Gradient Approach to the Quadratic Assignment Problem

  • Guoqing Zhang, prés., University of Windsor
  • Ebrahim Pichka, University of Windsor

  We present an approach to solving the Quadratic Assignment Problem (QAP) by formulating it as a Markov Decision Process (MDP) and applying Proximal Policy Optimization (PPO) within an Actor-Critic framework. The methodology employs Graph Attention Networks (GAT) to learn optimal policies using a bipartite graph representation of QAP. PPO agents were trained on problem instances of up to 50. Performance was evaluated against established baselines. Experiments demonstrate the scalability and efficacy of the proposed approach, particularly for relatively large-scale QAPs. The application of an improvement heuristic further enhances solution quality.