Publications

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. This paper extends our previously peel-and-bound approaches and close several benchmark instances on the traveling salesman problem with time windows problem

I. Rudich, Q. Cappart, L.-M. Rousseau

Journal of Artificial Intelligence Research (2023)

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring the fact that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks, as a key building block for combinatorial tasks. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at researchers in both optimization and machine learning

Q. Cappart, D. Chételat, E. Khalil, A. Lodi, C. Morris, P. Veličković

Journal of Machine Learning Research (2023)

Constraint programming is known for being an efficient approach for solving combinatorial problems. Important design choices in a solver are the branching heuristics, which are designed to lead the search to the best solutions in a minimum amount of time. This paper introduces a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network architecture.

T. Marty, T. François, P. Tessier, L. Gauthier, L.-M. Rousseau, Q. Cappart

Proceedings of CP 2023 conference (Distinguished paper)

With the rapid developments in communication systems, and considering their dynamic nature, all-optical networks are becoming increasingly complex. This paper proposes a novel method based on deep reinforcement learning for the routing and wavelength assignment problem in all-optical wavelength-decision-multiplexing networks. We employ graph neural networks to capture crucial latent information from the graph-structured input to develop the optimal strategy.

P. Kafaei, Q. Cappart, N. Chapados, H. Pouya, L.-M. Rousseau

INFORMS Journal on Optimization (2023)

Deep reinforcement learning algorithms are increasingly used to drive decision-making systems. However, there exists a known tension between the efficiency of a machine learning algorithm and its level of explainability. Generally speaking, increased efficiency comes with the cost of decisions that are harder to explain. This paper proposes to explain the behaviour of a deep reinforcement learning algorithm thanks to standard data mining tools, i.e. association rules. We apply this idea to the design of playing bots, which is ubiquitous in the video game industry.

Z. Parham, V.T. de Lille, Q. Cappart

Proceedings of LION 2023 conference

Managing a fleet of vehicles under uncertainty requires careful planning and adaptability. We consider a ride-hailing problem where the operator manages vehicle repositioning to maximize responsiveness. This paper introduces a supervised learning pipeline that uses past trip data to reposition vehicles while adapting to fleet activity, a geographical zone, and seasonal or daily request variation. This tool has been developed for, and used by, operators of an ambulance company in Belgium. Using predictors for ambulance repositioning reduces at least 10% of the overall fleet reaction distance.

A. Parjadis, Q. Cappart, Q. Massoteau, L.-M. Rousseau,

Proceedings of LION 2023 conference

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods.

I. Rudich, Q. Cappart, L.-M. Rousseau

Proceedings of CP 2022 conference (Best paper award)

Modern electrical power utilities must maintain their electrical equipment and replace it when the end of its useful life arrives. The Transmission Maintenance Scheduling (TMS) problem consists in generating an annual maintenance plan for electric power transportation equipment while maintaining the stability of the network and ensuring a continuous power flow for customers. Each year, a list of equipment (power lines, capacitors, transistors, etc.) that needs to be maintained or replaced is available and the goal is to generate an optimal maintenance plan. This paper proposes a constraint-based scheduling approach for solving the TMS problem.

L. Popovic, A. Côté, M. Gaha, F. Nguewouo, Q. Cappart

Proceedings of CP 2022 conference

This paper studies the use of reinforcement learning to compute a variable ordering of decision diagram-based approximations for discrete optimization problems. This is among the first works to propose the use of machine learning to improve upon generic bounding methods for discrete optimization problems, thereby establishing a critical bridge between optimization and learning.

Q. Cappart, D. Bergman, L.-M. Rousseau, I. Prémont-Schwarz, A. Parjadis

INFORMS Journal on Computing (2022)

End-to-end training of neural network solvers for combinatorial problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers for trivially small sizes, they are unable to generalize the learnt policy to larger instances. This paper proposes controlled experiments in the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the entire neural combinatorial optimization pipeline.

C. K. Joshi, Q. Cappart, L.-M. Rousseau, T. Laurent

Constraints Journal (2022)

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning as a new approach for solving combinatorial problems, either directly as solvers or by enhancing exact solvers. Based on this context, the ML4CO aims at improving state-of-the-art combinatorial optimization solvers by replacing key heuristic components.

M. Gasse, Q. Cappart, A. Parjadis, et al.

NeurIPS 2021 Competitions and Demonstrations Track

This paper presents a deep Q-learning approach based on graph neural networks to improve cancer treatments performed by the Cyberknife system.

P. Kafaei, Q. Cappart, M.-A. Renaud, N. Chapados, L.-M. Rousseau

Physics in Medicine & Biology Journal (2021)

This paper presents the proof of concept for SeaPearl, a new constraint programming solver implemented in Julia, that supports machine learning routines in order to learn branching decisions using reinforcement learning. Support for modeling the learning component is also provided.

F. Chalumeau, I. Coulon, Q. Cappart, L.-M. Rousseau

Proceedings of CPAIOR 2021 conference

We propose a general and hybrid approach, based on deep reinforcement learning and constraint programming, for solving combinatorial optimization problems. The core of the approach is based on a dynamic programming formulation, that acts as a bridge between both techniques.

Q. Cappart, T. Moisan, L.-M. Rousseau, I. Prémont-Schwarz, A. Cire

Proceedings of AAAI 2021 conference