4 présentations

• 
  10h30 - 10h55

  Reinforcement Learning-based Heuristics to Guide Domain Independent Dynamic Programming

  • Minori Narita, prés., University of Toronto
  • Ryo Kuroiwa, University of Toronto
  • J. Christopher Beck, University of Toronto

  Domain-Independent Dynamic Programming (DIDP) is a recently proposed generic state space search method based on dynamic programming. DIDP has outperformed mixed-integer programming and constraint programming across a number of combinatorial optimization problems and is thus a promising alternative to existing model-based solvers. One of the current challenges in DIDP is that there is little heuristic guidance. To make the search more efficient, we propose the integration of reinforcement learning (RL)-based heuristics to guide the search. A DIDP model has a favorable similarity to a Markov Decision Process (MDP), a formalism to define the environment explored by a reinforcement learning (RL) agent, encouraging the use of RL guidance. We propose two different ways to utilize RL-based heuristic values: one using a value-based approach (DQN) to obtain learned heuristic values, and one using a policy-based approach (PPO) to prioritize state transitions deemed promising by the RL agent. Our proof-of-concept experiments using common combinatorial optimization problems show that RL-guided heuristics help DIDP find better solutions with fewer node expansions in the initial stage of the search.

• 
  10h55 - 11h20

  Neural Sequence Generation with Cuts: A Case Study on VRP

  • Pouya Shati, prés., University of Toronto
  • Eldan Cohen, University of Toronto
  • Sheila McIlraith, University of Toronto

  Neural sequence models have recently been applied to solve combinatorial optimization problems. Solutions are typically generated from trained neural models using beam search (BS), a search algorithm that generates solutions as sequences of tokens while maintaining a set of promising partial solutions at each step. Beam search lacks the ability to guarantee satisfaction of hard constraints, a crucial component of many combinatorial problems. We propose extending BS to a modular framework that allows the generation of solutions that are guaranteed to satisfy given requirements, by encoding the requirements as constraint satisfaction problems (CSP). Beam search with cuts (BSC), iteratively solves the given CSP and cuts partial solutions that are incapable of satisfying the requirement. We evaluate our approach in the context of vehicle routing problems and focus on variants with capacity-related or temporal constraints. Our experiments show that cuts often allow requirement satisfaction with negligible impact on solution quality. We further show that BS is exponentially less likely than BSC to satisfy requirements as the length of the solution and/or the strength of the requirement is increased. Lastly, we show that incremental CSP solving can significantly improve the performance of BSC.

• 
  11h20 - 11h45

  Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches

  • Léo Boisvert, prés., Polytechnique Montréal
  • Quentin Cappart, Polytechnique Montréal
  • Hélène Verhaeghe, KULeuven

  In recent years, there has been a growing interest in using learning-based approaches for solving combinatorial problems, either in an end-to-end manner or in conjunction with traditional optimization algorithms. In both scenarios, the challenge lies in encoding the targeted combinatorial problems into a structure compatible with the learning algorithm. Many existing works have proposed problem-specific representations, often in the form of a graph, to leverage the advantages of Graph Neural Networks.
  However, these approaches lack generality, as the representation cannot be easily transferred from one combinatorial problem to another one. While some attempts have been made to bridge this gap, they still offer a partial generality only. In response to this challenge, our work advocates for progress toward a fully generic representation of combinatorial problems for learning-based approaches. The approach we propose involves constructing a graph by breaking down any constraint of a combinatorial problem into an abstract syntax tree and expressing relationships (e.g., a variable involved in a constraint) through the edges. Furthermore, we introduce a graph neural network architecture capable of efficiently learning from this representation. The tool provided operates on combinatorial problems expressed in the XCSP3 format, handling all the constraints available in the 2023 mini-track competition. Experimental results on four combinatorial problems demonstrate that our architecture achieves performance comparable to dedicated architectures while maintaining generality.

• 
  11h45 - 12h10

  A data-driven method for constraint customization in optimization models

  • Mahdis Bayani, Polytechnique Montreal
  • Yossiri Adulyasak, HEC Montréal
  • Louis-Martin Rousseau, prés., Polytechnique Montréal

  In numerous practical applications, optimization tools are often not readily adjustable or configurable by end users due to limited knowledge, resources, or the required investment to consistently make such customizations. One can leverage data-driven methods to learn and embed implicit side constraints as soft constraints in a mixed integer linear program (MILP) to ensure that such rules can be learned and systematically incorporated into optimization models.. To this end, we extend a data-driven constraint customization framework in the literature developed to extract constraints in the form of a traditional linear regression model to the case when constraints take the form of decision trees. This allows us to learn and incorporate customization constraints non-linearly or logically. Experiments were conducted on the knapsack and nurse rostering problems, where various combinations of hidden operational rules were simulated to demonstrate the value of this data-driven constraint customization framework. The solutions obtained by our proposed solution framework suggest that it can effectively adjust the solutions based on the constraints extracted from historical solutions. The customization constraints that take the form of decision trees generally outperform those based on linear regression models, especially when part of the decision model comprises discrete variables.