Grant: Discovery Grants Program - Individual
Université du Québec à Montréal
$32,000.00
Using machine learning to improve large-scale combinatorial optimization algorithms.
FY 2024-25
Summary
For more than 50 years, the field of operations research (OR) has developed a vast array of algorithms to optimize industrial and logistical planning. The use of OR tools has yielded immeasurable savings for Canadian companies. Some recent publications suggest combining machine learning (ML) with OR to speed-up the resolution of optimization problems. However, this field is still new, and few publications consider industrial applications. My Discovery research program aims to fill this gap. Along with graduate students and other HQPs, I plan to develop new optimization algorithms that combine ML and OR, with a focus on real-world applications. I have a vast experience of ML-enabled optimization, having lead several research projects in the field. I am therefore in an ideal position to carry out this research program.
The long-term goal of my research program is to develop ML-enabled optimization methods for a vast array of algorithms and applications. In the short term, I will focus on air crew scheduling problems, such as the aircrew pairing problem and the aircrew rostering problem. Those are complex large-scale combinatorial optimization problems that are well studied. They are therefore an excellent benchmark for developing ML-enabled optimization methods. My research program will achieve the following 4 objectives :
i) Creating high-quality initial solutions
Several OR algorithms, such as the simplex algorithm, require or can benefit from a high-quality initial solution. ML could be used to quickly produce such a solution.
ii) Reducing the search space
OR algorithms are sometimes slow due to the high number of poor-quality solutions that need to be discarded. Consider an employee scheduling problem for which the goal is to maximize employee satisfaction. Current optimization algorithms must consider all possible work shifts for each employee when many of these shifts are obviously undesirable. Instead, an ML model could restrict the problem's search space by selecting a subset of favorable shifts for each employee.
iii) Learning decision heuristics
Some OR algorithms use heuristics to make key decisions. For instance, a heuristic is used in the branch-and-bound algorithm to choose a variable to branch on. We will develop ML-based heuristics that outperform traditional ones and reach an optimal solution faster.
iv) Developing data analysis and forecasting tools
Some optimization problems require accurate estimates of parameters (e.g., customer demand for each day). Current estimation models are generally linear and consider only a few relevant factors. Using sophisticated ML models (such as a neural network), we could build more complex (non-linear) estimation models that would consider a large amount of data.
Using the developed ML-enabled methods, Canadian companies and public organisms will be able to solve more complex optimization problems, faster. This will lead to significant savings and more resource-efficient planning.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2023-04439
Name nom
Quesnel, Frédéric
Department département
Département d'analytique, opérations et technologies
Organization id
57
Institution établissement
Université du Québec à Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
32000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2804
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Expert systems
Research subject fr
Systèmes experts
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Using machine learning to improve large-scale combinatorial optimization algorithms.
Keywords
operations research; machine learning; transportation; integral simplex; large-scale problems; demand forecasting
Application summary
For more than 50 years, the field of operations research (OR) has developed a vast array of algorithms to optimize industrial and logistical planning. The use of OR tools has yielded immeasurable savings for Canadian companies. Some recent publications suggest combining machine learning (ML) with OR to speed-up the resolution of optimization problems. However, this field is still new, and few publications consider industrial applications. My Discovery research program aims to fill this gap. Along with graduate students and other HQPs, I plan to develop new optimization algorithms that combine ML and OR, with a focus on real-world applications. I have a vast experience of ML-enabled optimization, having lead several research projects in the field. I am therefore in an ideal position to carry out this research program.
The long-term goal of my research program is to develop ML-enabled optimization methods for a vast array of algorithms and applications. In the short term, I will focus on air crew scheduling problems, such as the aircrew pairing problem and the aircrew rostering problem. Those are complex large-scale combinatorial optimization problems that are well studied. They are therefore an excellent benchmark for developing ML-enabled optimization methods. My research program will achieve the following 4 objectives :
i) Creating high-quality initial solutions
Several OR algorithms, such as the simplex algorithm, require or can benefit from a high-quality initial solution. ML could be used to quickly produce such a solution.
ii) Reducing the search space
OR algorithms are sometimes slow due to the high number of poor-quality solutions that need to be discarded. Consider an employee scheduling problem for which the goal is to maximize employee satisfaction. Current optimization algorithms must consider all possible work shifts for each employee when many of these shifts are obviously undesirable. Instead, an ML model could restrict the problem's search space by selecting a subset of favorable shifts for each employee.
iii) Learning decision heuristics
Some OR algorithms use heuristics to make key decisions. For instance, a heuristic is used in the branch-and-bound algorithm to choose a variable to branch on. We will develop ML-based heuristics that outperform traditional ones and reach an optimal solution faster.
iv) Developing data analysis and forecasting tools
Some optimization problems require accurate estimates of parameters (e.g., customer demand for each day). Current estimation models are generally linear and consider only a few relevant factors. Using sophisticated ML models (such as a neural network), we could build more complex (non-linear) estimation models that would consider a large amount of data.
Using the developed ML-enabled methods, Canadian companies and public organisms will be able to solve more complex optimization problems, faster. This will lead to significant savings and more resource-efficient planning.