Portrait of Quentin Cappart

Quentin Cappart

Affiliate Member
Associate Professor, Polytechnique Montréal
Research Topics
Graph Neural Networks
Learning on Graphs
Reasoning

Biography

Quentin Cappart is an associate professor in the Department of Computer and Software Engineering at Polytechnique Montréal and an Affiliate member at Mila. He leads the CORAIL research group, which he co-founded with Louis-Martin Rousseau. Cappart obtained a BSc in engineering (2012), a MSc in computer engineering (2014), a MSc in management (2018) and a PhD (2017) at the Université catholique de Louvain (Belgium).

After his PhD, he joined Polytechnique Montréal and the International Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) as a postdoctoral fellow (2018–2020). During these two years, he was also a research intern at ElementAI. Cappart’s main research area is the integration of machine learning with search procedures for solving combinatorial problems.

Current Students

PhD - Polytechnique Montréal
Principal supervisor :

Publications

WorkArena++: Towards Compositional Planning and Reasoning-based Common Knowledge Work Tasks
The ability of large language models (LLMs) to mimic human-like intelligence has led to a surge in LLM-based autonomous agents. Though recen… (see more)t LLMs seem capable of planning and reasoning given user instructions, their effectiveness in applying these capabilities for autonomous task solving remains underexplored. This is especially true in enterprise settings, where automated agents hold the promise of a high impact. To fill this gap, we propose WorkArena++, a novel benchmark consisting of 682 tasks corresponding to realistic workflows routinely performed by knowledge workers. WorkArena++ is designed to evaluate the planning, problem-solving, logical/arithmetic reasoning, retrieval, and contextual understanding abilities of web agents. Our empirical studies across state-of-the-art LLMs and vision-language models (VLMs), as well as human workers, reveal several challenges for such models to serve as useful assistants in the workplace. In addition to the benchmark, we provide a mechanism to effortlessly generate thousands of ground-truth observation/action traces, which can be used for fine-tuning existing models. Overall, we expect this work to serve as a useful resource to help the community progress toward capable autonomous agents. The benchmark can be found at https://github.com/ServiceNow/WorkArena.
Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver
Tristan François
Pierre Tessier
Louis Gautier
Louis-Martin Rousseau
Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are … (see more)the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. We propose to tackle this issue by introducing 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. Experiments on graph coloring, maximum independent set, maximum cut, and minimum vertex cover problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks. Additionally, we observe that fine-tuning a model with a different problem class can accelerate the learning process.
Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning
Swann Bessa
Darius Dabert
Max Bourgeat
Louis-Martin Rousseau
WorkArena: How Capable are Web Agents at Solving Common Knowledge Work Tasks?
We study the use of large language model-based agents for interacting with software via web browsers. Unlike prior work, we focus on measuri… (see more)ng the agents' ability to perform tasks that span the typical daily work of knowledge workers utilizing enterprise software systems. To this end, we propose WorkArena, a remote-hosted benchmark of 33 tasks based on the widely-used ServiceNow platform. We also introduce BrowserGym, an environment for the design and evaluation of such agents, offering a rich set of actions as well as multimodal observations. Our empirical evaluation reveals that while current agents show promise on WorkArena, there remains a considerable gap towards achieving full task automation. Notably, our analysis uncovers a significant performance disparity between open and closed-source LLMs, highlighting a critical area for future exploration and development in the field.
Global rewards in multi-agent deep reinforcement learning for autonomous mobility on demand systems
Heiko Hoppe
Tobias Enders
Maximilian Schiffer
We study vehicle dispatching in autonomous mobility on demand (AMoD) systems, where a central operator assigns vehicles to customer requests… (see more) or rejects these with the aim of maximizing its total profit. Recent approaches use multi-agent deep reinforcement learning (MADRL) to realize scalable yet performant algorithms, but train agents based on local rewards, which distorts the reward signal with respect to the system-wide profit, leading to lower performance. We therefore propose a novel global-rewards-based MADRL algorithm for vehicle dispatching in AMoD systems, which resolves so far existing goal conflicts between the trained agents and the operator by assigning rewards to agents leveraging a counterfactual baseline. Our algorithm shows statistically significant improvements across various settings on real-world data compared to state-of-the-art MADRL algorithms with local rewards. We further provide a structural analysis which shows that the utilization of global rewards can improve implicit vehicle balancing and demand forecasting abilities. An extended version of our paper, including an appendix, can be found at https://arxiv.org/abs/2312.08884. Our code is available at https://github.com/tumBAIS/GR-MADRL-AMoD.
An Improved Neuro-Symbolic Architecture to Fine-Tune Generative AI Systems
Gilles Pesant
Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches
Hélène Verhaeghe
Deep Learning for Data-Driven Districting-and-Routing
Arthur Ferraz
Cheikh Ahmed
Thibaut Vidal
Dynamic Routing and Wavelength Assignment with Reinforcement Learning.
Peyman Kafaei
Hamed Pouya
Louis-Martin Rousseau
With the rapid developments in communication systems, and considering their dynamic nature, all-optical networks are becoming increasingly c… (see more)omplex. This study proposes a novel method based on deep reinforcement learning for the routing and wavelength assignment problem in all-optical wavelength-decision-multiplexing networks. We consider dynamic incoming requests, in which their arrival and holding times are not known in advance. The objective is to devise a strategy that minimizes the number of rejected packages due to the lack of resources in the long term. We use graph neural networks to capture crucial latent information from the graph-structured input to develop the optimal strategy. The proposed deep reinforcement learning algorithm selects a route and a wavelength simultaneously for each incoming traffic connection as they arrive. The results demonstrate that the learned agent outperforms the methods used in practice and can be generalized on network topologies that did not participate in training.
Learning Lagrangian Multipliers for the Travelling Salesman Problem
Augustin Parjadis
Bistra Dilkina
Aaron M. Ferber
Louis-Martin Rousseau
Learning Precedences for Scheduling Problems with Graph Neural Networks
Hélène Verhaeghe
Gilles Pesant
Claude-Guy Quimper
Winning the 2023 CityLearn Challenge: A Community-Based Hierarchical Energy Systems Coordination Algorithm
Andoni I. Garmendia
Hélène Le Cadre
. The effective management and control of building energy systems are crucial for reducing the energy consumption peak loads, CO 2 emissions… (see more), and ensuring the stability of the power grid, while maintaining optimal comfort levels within buildings. The difficulty to accommodate this trade-off is amplified by dynamic environmental conditions and the need for scalable solutions that can adapt across various building types and geographic locations. Acknowledging the importance of this problem, NeurIPS conference hosted since 2020 the CityLearn control challenge to foster the design of innovative solutions in building energy management. Participants were tasked with developing strategies that not only enhance energy efficiency but also prioritize sustainability and occupant comfort. This paper introduces the Community-based Hierarchical Energy Systems Co-ordination Algorithm ( CHESCA ), the winning approach of the 2023 edition. We rely on a hierarchical approach adaptable to an arbitrary number of buildings, first optimizing building-level metrics individually, and later refining these through a central community-level controller to improve grid-related metrics. Compared to the other high-ranked competitors, our approach demonstrated fast inference capabilities like learning-based methods, while offering a better interpretability and a superior generalization capabilities with minimal data requirements. This paper details our approach, supported by comprehensive experimental results and ablation studies.