Antoine Legrain

Prakash Gawas, Antoine Legrain, Louis-Martin Rousseau

Imitation learning (IL) provides a data-driven framework for approximating policies for large-scale combinatorial optimisation problems formulated as sequential decision problems (SDPs), where exact solution methods are computationally intractable. A central but underexplored aspect of IL in this context is the role of the \emph{expert} that generates training demonstrations. Existing studies employ a wide range of expert constructions, yet lack a unifying framework to characterise their modelling assumptions, computational properties, and impact on learning performance. This paper introduces a systematic taxonomy of experts for imitation learning in combinatorial optimisation under uncertainty. The literature is classified along three principal dimensions: (i) treatment of uncertainty; (ii) level of optimality, distinguishing task-optimal and approximate experts; and (iii) interaction mode with the learner, ranging from one-shot supervision to iterative, interactive schemes. We further identify additional categories capturing other relevant expert characteristics. Building on this taxonomy, we propose a generalised Dataset Aggregation (DAgger) framework that accommodates multiple expert queries, expert aggregation, and flexible interaction strategies. The proposed framework is evaluated on a dynamic physician-to-patient assignment problem with stochastic arrivals and capacity constraints. Computational experiments compare learning outcomes across expert types and interaction regimes. The results show that policies learned from stochastic experts consistently outperform those learned from deterministic or full-information experts, while interactive learning improves solution quality using fewer expert demonstrations. Aggregated deterministic experts provide an effective alternative when stochastic optimisation becomes computationally challenging.

Tu-San Pham, Antoine Legrain, Patrick De Causmaecker et al.

Patient scheduling is a difficult task involving stochastic factors such as the unknown arrival times of patients. Similarly, the scheduling of radiotherapy for cancer treatments needs to handle patients with different urgency levels when allocating resources. High priority patients may arrive at any time, and there must be resources available to accommodate them. A common solution is to reserve a flat percentage of treatment capacity for emergency patients. However, this solution can result in overdue treatments for urgent patients, a failure to fully exploit treatment capacity, and delayed treatments for low-priority patients. This problem is especially severe in large and crowded hospitals. In this paper, we propose a prediction-based approach for online dynamic radiotherapy scheduling that dynamically adapts the present scheduling decision based on each incoming patient and the current allocation of resources. Our approach is based on a regression model trained to recognize the links between patients' arrival patterns, and their ideal waiting time in optimal offline solutions where all future arrivals are known in advance. When our prediction-based approach is compared to flat-reservation policies, it does a better job of preventing overdue treatments for emergency patients, while also maintaining comparable waiting times for the other patients. We also demonstrate how our proposed approach supports explainability and interpretability in scheduling decisions using SHAP values.

Mohd Hafiz Hasan, Pascal Van Hentenryck, Antoine Legrain

Parking pressure has been steadily increasing in cities as well as in university and corporate campuses. To relieve this pressure, this paper studies a car-pooling platform that would match riders and drivers, while guaranteeing a ride back and exploiting spatial and temporal locality. In particular, the paper formalizes the Commute Trip Sharing Problem (CTSP) to find a routing plan that maximizes ride sharing for a set of commute trips. The CTSP is a generalization of the vehicle routing problem with routes that satisfy time window, capacity, pairing, precedence, ride duration, and driver constraints. The paper introduces two exact algorithms for the CTPS: A route-enumeration algorithm and a branch-and-price algorithm. Experimental results show that, on a high-fidelity, real-world dataset of commute trips from a mid-size city, both algorithms optimally solve small and medium-sized problems and produce high-quality solutions for larger problem instances. The results show that car pooling, if widely adopted, has the potential to reduce vehicle usage by up to 57% and decrease vehicle miles traveled by up to 46% while only incurring a 22% increase in average ride time per commuter for the trips considered.