Optimization Days 2024
HEC Montréal, Québec, Canada, 6 — 8 May 2024
WB3 - Machine learning for optimization II
May 8, 2024 03:30 PM – 05:10 PM
Location: METRO INC. (yellow)
Chaired by Arthur Charpentier
4 Presentations
-
03:30 PM - 03:55 PM
LEO: Learning Efficient Orderings for Multiobjective Binary Decision Diagrams
Approaches based on Binary decision diagrams (BDDs) have recently achieved state-of-the-art results for multiobjective integer programming problems. The variable ordering used in constructing BDDs can have a significant impact on their size and on the quality of bounds derived from relaxed or restricted BDDs for single-objective optimization problems. We first showcase a similar impact of variable ordering on the Pareto frontier (PF) enumeration time for the multiobjective knapsack problem, suggesting the need for deriving variable ordering methods that improve the scalability of the multiobjective BDD approach. To that end, we derive a novel parameter configuration space based on variable scoring functions which are linear in a small set of interpretable and easy-to-compute variable features. We show how the configuration space can be efficiently explored using black-box optimization, circumventing the curse of dimensionality (in the number of variables and objectives), and finding good orderings that reduce the PF enumeration time. However, black-box optimization approaches incur a computational overhead that outweighs the reduction in time due to good variable ordering. To alleviate this issue, we propose LEO, a supervised learning approach for finding efficient variable orderings that reduce the enumeration time. Experiments on benchmark sets from the knapsack problem with 3-7 objectives and up to 80 variables show that LEO is 3x and 1.3x faster at PF enumeration than lexicographic ordering and algorithm configuration, respectively. Our code and instances are available at https://github.com/khalil-research/leo.
-
03:55 PM - 04:20 PM
Improving E-commerce Air Cargo Efficiency through Predictive Machine Learning Models
This PhD project is associated with a subsection of an airline, focused on enhancing the precision of air cargo forecasts for e-commerce goods. Utilizing advanced machine learning techniques, specifically time series forecasting, the research aims to predict future cargo requirements by analyzing historical data trends. A novel aspect of this study is the integration of unconventional data sources like Google Trends, which provides insights into public interest patterns. The methodology employs state-of-the-art algorithms like Temporal Fusion Transformers (TFT). These tools are adept at identifying and learning from temporal sequences in data, making them ideal for forecasting applications where understanding time-based patterns. A key innovation of this work a new approach to initializing the forecasting models. By recognizing the predictive value of weekly cargo demand patterns for the upcoming month, the models are equipped with a more informed starting point. This not only enhances the models' predictive accuracy but also accelerates their learning process. The implications of this research could be significant for the airline, enabling more efficient and responsive cargo space allocation for e-commerce goods. By leveraging data analysis and machine learning techniques, the study offers an avenue for improving operational efficiency and cost-effectiveness in air cargo logistics.
-
04:20 PM - 04:45 PM
A two phase iterative approach using machine learning to solve a gas pipeline surveillance problem.
GRTgaz is the natural gas transmission system’s operator in France. To guarantee the safety of its gas infrastructures, the company conducts daily surveillance tours. These involve navigating the entire network to identify any anomalies that could damage the installations. These tours are planned and carried out every year. The network is divided into sections of pipe, each with its own surveillance mode (car, plane, etc.) and a frequency of visits per year depending on the risk involved. This problem is defined as a Periodic Capacitated Arc Routing Problem (PCARP) with a multi modal fleet. It is NP-hard because it is an extension of the CARP, which is NP-hard. To solve this problem, we develop a two-phase iterative approach supported by a machine learning model. The aim of the first phase, known as Scheduling, is to allocate the sections to be monitored to weeks of the year and to a monitoring mode, respecting the frequency constraints; the aim of the second phase, known as Routing, is to build the routes for each week of the year and each mode. A machine learning model assists the Scheduling phase by estimating the costs of the routes depending on the edges included to monitor.
-
04:45 PM - 05:10 PM
Market Pricing with Reinforcement Learning
Several recent articles have attempted to gain a better understanding of algorithmic collusion (Calvano et al. (2020), Klein (2021), Banchio & Mantegazza (2022) Rocher et al. (2023)). For example, in Calvano et al. (2020), a simulation study showed that for a simplified market environment, basic Q-Learning Agents can learn to collude tacitly, in order to propose higher prices and increase their combined profit. Inspired by some Iterated Prisoners Dilemma, we derive some reinforcement learning algorithm to investigate and discuss several recent results and their robustness, and explain how reinforcement learning differs from simpler strategies and which conditions lead to unfavorable outcomes from a consumer perspective. In particular, we first describe the reinforcement learning problem in a more general manner and investigate the influence of the hyper-parameters. We then consider two situations separately. One, similar in spirit to Rocher et al. (2023), assumes that the market is in equilibrium and that a general agent tries to exploit a pricing strategy of an incumbent agent. The second, more general, approach consists of an agent continuously updating their own policy.