Emma Frejinger

2024-06-30

Operations Research Forum (published)

Reinforcement learning for freight booking control problems

Justin Dumouchelle

Andrea Lodi

2024-03-15

Journal of Revenue and Pricing Management (published)

Decoupling regularization from the action space

Sobhan Mohammadpour

Pierre-Luc Bacon

Regularized reinforcement learning (RL), particularly the entropy-regularized kind, has gained traction in optimal control and inverse RL. W… (see more)hile standard unregularized RL methods remain unaffected by changes in the number of actions, we show that it can severely impact their regularized counterparts. This paper demonstrates the importance of decoupling the regularizer from the action space: that is, to maintain a consistent level of regularization regardless of how many actions are involved to avoid over-regularization. Whereas the problem can be avoided by introducing a task-specific temperature parameter, it is often undesirable and cannot solve the problem when action spaces are state-dependent. In the state-dependent action context, different states with varying action spaces are regularized inconsistently. We introduce two solutions: a static temperature selection approach and a dynamic counterpart, universally applicable where this problem arises. Implementing these changes improves performance on the DeepMind control suite in static and dynamic temperature regimes and a biological design task.

2024-01-15

ICLR.cc/2024/Conference (poster)

openreview.net

Maximum entropy GFlowNets with soft Q-learning

Sobhan Mohammadpour

Emmanuel Bengio

Pierre-Luc Bacon

Generative Flow Networks (GFNs) have emerged as a powerful tool for sampling discrete objects from unnormalized distributions, offering a sc… (see more)alable alternative to Markov Chain Monte Carlo (MCMC) methods. While GFNs draw inspiration from maximum entropy reinforcement learning (RL), the connection between the two has largely been unclear and seemingly applicable only in specific cases. This paper addresses the connection by constructing an appropriate reward function, thereby establishing an exact relationship between GFNs and maximum entropy RL. This construction allows us to introduce maximum entropy GFNs, which, in contrast to GFNs with uniform backward policy, achieve the maximum entropy attainable by GFNs without constraints on the state space.

2023-12-31

AISTATS (published)

proceedings.mlr.press

Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems

Eric Larsen

Serge Bisaillon

Jean-François Cordeau

Network design problems constitute an important family of combinatorial optimization problems for which numerous exact and heuristic algorit… (see more)hms have been developed over the last few decades. Two central problems in this family are the multi-commodity, capacitated, fixed charge network design problem (MCFNDP) and its stochastic counterpart, the two-stage MCFNDP with recourse. These are standard problems that often serve as work benches for devising and testing models and algorithms in stylized but close-to-realistic settings. The purpose of this paper is to introduce two flexible, high-speed generators capable of simulating a wide range of settings for both the deterministic and stochastic MCFNDPs. We hope that, by facilitating systematic experimentation with new and larger sets of instances, these generators will lead to a more thorough assessment of the performance achieved by exact and heuristic solution methods in both deterministic and stochastic settings. We also hope that making these generators available will promote the reproducibility and comparability of published research.

2023-12-16

ArXiv (preprint)

Scope Restriction for Scalable Real-Time Railway Rescheduling: An Exploratory Study

Erik L. Nygren

Christian Eichenberger

With the aim to stimulate future research, we describe an exploratory study of a railway rescheduling problem. A widely used approach in pra… (see more)ctice and state of the art is to decompose these complex problems by geographical scope. Instead, we propose defining a core problem that restricts a rescheduling problem in response to a disturbance to only trains that need to be rescheduled, hence restricting the scope in both time and space. In this context, the difficulty resides in defining a scoper that can predict a subset of train services that will be affected by a given disturbance. We report preliminary results using the Flatland simulation environment that highlights the potential and challenges of this idea. We provide an extensible playground open-source implementation based on the Flatland railway environment and Answer-Set Programming.

2023-05-04

ArXiv (preprint)

Optimising Electric Vehicle Charging Station Placement using Advanced Discrete Choice Models

Steven Lamontagne

Margarida Carvalho

Bernard Gendron

Miguel F. Anjos

Ribal Atallah

D'epartement d'informatique et de recherche op'erationnelle

U. Montr'eal

S. O. Mathematics

U. Edinburgh

Institut de Recherche d'Hydro-Qu'ebec

We present a new model for finding the optimal placement of electric vehicle charging stations across a multi-period time frame so as to max… (see more)imise electric vehicle adoption. Via the use of advanced discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. Instead of embedding an analytical probability model in the formulation, we adopt a simulation approach and pre-compute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Using the pre-computed error terms to calculate the users covered by each charging station allows for a maximum covering model, for which solutions can be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and GRASP heuristics to obtain good quality solutions more efficiently. Extensive computational results are provided, which compare the maximum covering formulation with the current state-of-the-art, both for exact solutions and the heuristic methods. Keywords: Electric vehicle charging stations, facility location, integer programming, discrete choice models, maximum covering

2022-12-31

INFORMS J. Comput. (published)

Undiscounted Recursive Path Choice Models: Convergence Properties and Algorithms

Tien Mai

2022-10-31

Transportation Science (published)

Arc travel time and path choice model estimation subsumed

Sobhan Mohammadpour

We propose a method for maximum likelihood estimation of path choice model parameters and arc travel time using data of diﬀerent levels of… (see more) granularity. Hitherto these two tasks have been tackled separately under strong assumptions. Using a small example, we illustrate that this can lead to biased results. Results on both real (New York yellow cab) and simulated data show strong performance of our method compared to existing baselines. models and loss functions. It is designed to estimate arc travel time and path choice model parameters simultaneously. We showed that by marginalizing the unobserved variables and using stochastic gradient estimates, we obtain a maximum likelihood estimation even for observations at diﬀerent level of granularity. We showed that we can mix diﬀerent data type when computing the MLE without needing to use a linear combination of losses as

2022-10-24

ArXiv (preprint)

The load planning and sequencing problem for double-stack trains

Moritz Ruf

Jean-François Cordeau

2022-08-31

Journal of Rail Transport Planning & Management (published)

Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning

Eric Larsen

Bernard Gendron

Andrea Lodi

We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to… (see more) accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time, for example, in transport planning related to fleet management, routing and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP the same figure is 20%. Average optimality gaps are in most cases less than 0.1%.

2022-05-01

ArXiv (preprint)

A time-space formulation for the locomotive routing problem at the Canadian National Railways

Pedro L. Miranda

Jean-François Cordeau

2022-02-28

Computers & Operations Research (published)