Emma Frejinger

Jean-François Cordeau

Current state-of-the-art solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems. Howe… (voir plus)ver, for many real-world use cases, problem instances come from a narrow distribution. This has motivated the development of specialized methods that can exploit the information in historical datasets to guide the design of heuristics. Recent works have shown that machine learning (ML) can be integrated with an MIP solver to inject domain knowledge and efficiently close the optimality gap. This hybridization is usually done with deep learning (DL), which requires a large dataset and extensive hyperparameter tuning to perform well. This paper proposes an online heuristic that uses the notion of entropy to efficiently build a model with minimal training data and tuning. We test our method on the locomotive assignment problem (LAP), a recurring real-world problem that is challenging to solve at scale. Experimental results show a speed up of an order of magnitude compared to a general purpose solver (CPLEX) with a relative gap of less than 2%. We also observe that for some instances our method can discover better solutions than CPLEX within the time limit.

2022-02-06

ArXiv (prépublication)

Data-Driven Combinatorial Optimisation (Dagstuhl Seminar 22431)

Andrea Lodi

Michele Lombardi

Neil Yorke-Smith

Machine learning’s impressive achievements in the last decade have urged many scientific communities to ask if and how the techniques deve… (voir plus)loped in that field to leverage data could be used to advance research in others. The combinatorial optimisation community is one of those

2021-12-31

Dagstuhl Reports (publié)

Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information

Eric Larsen

Andrea Lodi

This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a method… (voir plus)ology to quickly predict tactical solutions to a given operational problem. In this context, the tactical solution is less detailed than the operational one but it has to be computed in very short time and under imperfect information. The problem is of importance in various applications where tactical and operational planning problems are interrelated and information about the operational problem is revealed over time. This is for instance the case in certain capacity planning and demand management systems. We formulate the problem as a two-stage optimal prediction stochastic program whose solution we predict with a supervised machine learning algorithm. The training data set consists of a large number of deterministic (second stage) problems generated by controlled probabilistic sampling. The labels are computed based on solutions to the deterministic problems (solved independently and offline) employing appropriate aggregation and subselection methods to address uncertainty. Results on our motivating application in load planning for rail transportation show that deep learning algorithms produce highly accurate predictions in very short computing time (milliseconds or less). The prediction accuracy is comparable to solutions computed by sample average approximation of the stochastic program.

2021-09-20

INFORMS Journal on Computing (inconnu)

Routing policy choice prediction in a stochastic network: Recursive model and solution algorithm

Tien Mai

Xinlian Yu

Song Gao

2021-08-31

Transportation Research Part B: Methodological (publié)

A Two-step Heuristic for the Periodic Demand Estimation Problem

Greta Laage

Gilles Savard

Freight carriers rely on tactical plans to satisfy demand in a cost-effective way. For computational tractability in real large-scale settin… (voir plus)gs, such plans are typically computed by solving deterministic and cyclic formulations. An important input is the periodic demand, i.e., the demand that is expected to repeat in each period of the planning horizon. Motivated by the discrepancy between time series forecasts of demand in each period and the periodic demand, Laage et al. (2021) recently introduced the Periodic Demand Estimation (PDE) problem and showed that it has a high value. However, they made strong assumptions on the solution space so that the problem could be solved by enumeration. In this paper we significantly extend their work. We propose a new PDE formulation that relaxes the strong assumptions on the solution space. We solve large instances of this formulation with a two-step heuristic. The first step reduces the dimension of the feasible space by performing clustering of commodities based on instance-specific information about demand and supply interactions. The formulation along with the first step allow to solve the problem in a second step by either metaheuristics or the state-of-the-art black-box optimization solver NOMAD. In an extensive empirical study using real data from the Canadian National Railway Company, we show that our methodology produces high quality solutions and outperforms existing ones.

2021-08-17

ArXiv (prépublication)

Periodic Freight Demand Estimation for Large-scale Tactical Planning

Greta Laage

Gilles Savard

Freight carriers rely on tactical planning to design their service network to satisfy demand in a cost-effective way. For computational trac… (voir plus)tability, deterministic and cyclic Service Network Design (SND) formulations are used to solve large-scale problems. A central input is the periodic demand, that is, the demand expected to repeat in every period in the planning horizon. In practice, demand is predicted by a time series forecasting model and the periodic demand is the average of those forecasts. This is, however, only one of many possible mappings. The problem consisting in selecting this mapping has hitherto been overlooked in the literature. We propose to use the structure of the downstream decision-making problem to select a good mapping. For this purpose, we introduce a multilevel mathematical programming formulation that explicitly links the time series forecasts to the SND problem of interest. The solution is a periodic demand estimate that minimizes costs over the tactical planning horizon. We report results in an extensive empirical study of a large-scale application from the Canadian National Railway Company. They clearly show the importance of the periodic demand estimation problem. Indeed, the planning costs exhibit an important variation over different periodic demand estimates and using an estimate different from the mean forecast can lead to substantial cost reductions. Moreover, the costs associated with the periodic demand estimates based on forecasts were comparable to, or even better than those obtained using the mean of actual demand.

2021-05-18

ArXiv (prépublication)

A Strategic Markovian Traffic Equilibrium Model for Capacitated Networks

Maëlle Zimmermann

Patrice Marcotte

In the realm of traffic assignment over a network involving rigid arc capacities, the aim of the present work is to generalize the model of … (voir plus)Marcotte, Nguyen, and Schoeb [Marcotte P, Nguyen S, Schoeb A (2004) A strategic flow model of traffic assignment in static capacitated networks. Oper. Res. 52(2):191–212.] by casting it within a stochastic user equilibrium framework. The strength of the proposed model is to incorporate two sources of stochasticity stemming, respectively, from the users’ imperfect knowledge regarding arc costs (represented by a discrete choice model) and the probability of not accessing saturated arcs. Moreover, the arc-based formulation extends the Markovian traffic equilibrium model of Baillon and Cominetti [Baillon JB, Cominetti R ( 2008 ) Markovian traffic equilibrium. Math. Programming 111(1-2):33–56.] through the explicit consideration of capacities. This paper is restricted to the case of acyclic networks, for which we present solution algorithms and numerical experiments.

2021-04-30

Transportation Science (publié)

Integrated inbound train split and load planning in an intermodal railway terminal

Bruno Petrato Bruck

Jean-François Cordeau

2021-02-28

Transportation Research Part B: Methodological (publié)

Assessing the Impact: Does an Improvement to a Revenue Management System Lead to an Improved Revenue?

Greta Laage

William L. Hamilton

Andrea Lodi

Guillaume Rabusseau

Airlines and other industries have been making use of sophisticated Revenue Management Systems to maximize revenue for decades. While improv… (voir plus)ing the different components of these systems has been the focus of numerous studies, estimating the impact of such improvements on the revenue has been overlooked in the literature despite its practical importance. Indeed, quantifying the benefit of a change in a system serves as support for investment decisions. This is a challenging problem as it corresponds to the difference between the generated value and the value that would have been generated keeping the system as before. The latter is not observable. Moreover, the expected impact can be small in relative value. In this paper, we cast the problem as counterfactual prediction of unobserved revenue. The impact on revenue is then the difference between the observed and the estimated revenue. The originality of this work lies in the innovative application of econometric methods proposed for macroeconomic applications to a new problem setting. Broadly applicable, the approach benefits from only requiring revenue data observed for origin-destination pairs in the network of the airline at each day, before and after a change in the system is applied. We report results using real large-scale data from Air Canada. We compare a deep neural network counterfactual predictions model with econometric models. They achieve respectively 1% and 1.1% of error on the counterfactual revenue predictions, and allow to accurately estimate small impacts (in the order of 2%).

2020-12-31

arXiv.org (prépublication)

The Locomotive Assignment Problem with Distributed Power at the Canadian National Railway Company

Camilo Ortiz-Astorquiza

Jean-François Cordeau

Some of the most important optimization problems faced by railway operators arise from the management of their locomotive fleet. In this pap… (voir plus)er, we study a general version of the locomotive assignment problem encountered at the tactical level by one of the largest railroads in North America: the Canadian National Railway Company (CN). We present a modeling framework with two integer linear programming formulations and contribute to the state of the art by allowing to decide each train's operating mode (distributed power or not) over the whole (weekly) planning horizon without partitioning it into smaller time windows. Given the difficulty to solve the problem, one of the formulations is enhanced through various refinements such as constraint relaxations, preprocessing and fixed cost approximations. We thus achieve a significant reduction in the required computational time to solve instances of realistic size. We also present two versions of a Benders decomposition-based algorithm to obtain feasible solutions. On average, it allows to reduce the associated computational time by two hours. Results from an extensive computational study and a case study with data provided by CN confirm the potential benefits of the model and solution approach.

2020-12-31

Transportation Science (publié)

A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs

Yoshua Bengio

Andrea Lodi

Rahul Patel

Sriram Sankaranarayanan

We propose a novel approach using supervised learning to obtain near-optimal primal solutions for two-stage stochastic integer programming (… (voir plus)2SIP) problems with constraints in the first and second stages. The goal of the algorithm is to predict a "representative scenario" (RS) for the problem such that, deterministically solving the 2SIP with the random realization equal to the RS, gives a near-optimal solution to the original 2SIP. Predicting an RS, instead of directly predicting a solution ensures first-stage feasibility of the solution. If the problem is known to have complete recourse, second-stage feasibility is also guaranteed. For computational testing, we learn to find an RS for a two-stage stochastic facility location problem with integer variables and linear constraints in both stages and consistently provide near-optimal solutions. Our computing times are very competitive with those of general-purpose integer programming solvers to achieve a similar solution quality.

2020-09-18

Integration of Constraint Programming, Artificial Intelligence, and Operations Research (publié)

Route choice behaviour and travel information in a congested network: Static and dynamic recursive models

G. M. Ramos

Tien Mai

W. Daamen

S. Hoogendoorn

2020-04-30

Transportation Research Part C: Emerging Technologies (publié)