Publications

Lagrangian relaxation is a versatile mathematical technique employed to relax constraints in an optimization problem, enabling the generation of dual bounds to prove the optimality of feasible solutions and the design of efficient propagators in constraint programming (such as the weighted circuit constraint). However, the conventional process of deriving Lagrangian multipliers (e.g., using subgradient methods) is often computationally intensive, limiting its practicality for large-scale or time-sensitive problems. To address this challenge, we propose an innovative unsupervised learning approach that harnesses the capabilities of graph neural networks to exploit the problem structure, aiming to generate accurate Lagrangian multipliers efficiently.

A. Parjadis, Q. Cappart, B. Dilkina, A. Ferber, L.-M. Rousseau

Proceedings of CP 2024 conference (Best ML paper award)

A preliminary estimation of construction costs is a crucial operation of any project related to civil engineering. An accurate estimation ensures a proper management of the available funds and helps the project managers in their decision-making processes. In order to select a subcontractor, the project manager needs to have an accurate idea of a reasonable price for the subtask given. A price higher than expected is undesirable, but a price significantly lower than expected may also result in poor quality of service. This paper introduces a framework for estimating construction costs while tackling both challenges. It is based on six machine learning models and on Shapley additive explanations. This project was commissioned by the Ministry of Transport and Sustainable Mobility, a public agency responsible for transport infrastruc- ture in Quebec, Canada.

R. Larocque, A.-M. Boulé, Q. Cappart

INFORMS Journal on Applied Analytics (2024)

Modern electrical power utilities must maintain their electrical equipment and replace it when the end of its useful life arrives. 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. While most constraints can be naturally formalized in constraint programming (CP), there are some complex constraints like transit-power limits that are challenging to model because of their continuous and non-linear nature. This paper proposes a methodology based on active constraint acquisition to automatically approximate these constraints and to add them into a CP model.

H. Barral, M. Gaha, A. Dems, A. Côté, F. Nguewouo, Q. Cappart

Proceedings of CPAIOR 2024 conference

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. this paper 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.

L. Boisvert, H. Verhaeghe, Q. Cappart

Proceedings of CPAIOR 2024 conference

Neural Combinatorial Optimization (NCO) is an emerging domain where deep learning techniques are employed to address combinatorial optimization problems as a standalone solver. Despite their potential, existing NCO methods often suffer from inefficient search space exploration, frequently leading to local optima entrapment or redundant exploration of previously visited states. This paper introduces a versatile framework that can be used to enhance both constructive and improvement methods in NCO through an innovative memory module.

A. Garmendia, J. Ceberio, A. Mendiburu, Q. Cappart

Proceedings of IJCAI 2024 conference

We study the use of large language model-based agents for interacting with software via web browsers. Unlike prior work, we focus on measuring 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 29 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.

A. Drouin, M. Gasse, M. Caccia, I. Laradji, M. Del Verme, T. Marty, L. Boisvert, M. Thakkar, Q. Cappart, D. Vazquez, N. Chapados, A. Lacoste

ICLR 2024 Workshop on Large Language Model (LLM) Agent

Bus scheduling in public transit consists in determining a set of bus schedules to cover a set of timetabled trips at minimum cost. Column-generation algorithms have regained popularity for solving problems similar to the one considered in this paper, namely, the multi-depot electric vehicle scheduling problem (MDEVSP) with a piecewise linear charging function and capacitated charging stations. To tackle large-scale MDEVSP instances, we design a learning-based column generation heuristic that relies on reduced-sized networks to generate the bus schedules

J. Gerbaux, Q. Cappart, G. Desaulniers

Les Cahiers du GERAD (2024)

We study vehicle dispatching in autonomous mobility on demand (AMoD) systems, where a cen- tral operator assigns vehicles to customer requests 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 re- ward 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 sys- tems, which resolves so far existing goal conflicts between the trained agents and the operator by assigning rewards to agents leveraging a counterfactual baseline

H. Hoppe, T. Enders, Q. Cappart, M. Schiffer

Proceedings of L4DC conference (to appear)

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