Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université Laval

$41,000.00

Filtering Algorithms Based on Lagrangian Relaxation

FY 2023-24

Summary
Constraint programming emerged from artificial intelligence to become a paradigm for solving hard combinatorial problems such as scheduling problems. These problems are modeled with variables, constraints over these variables, and an objective function and are submitted to a constraint solver, a program able to return a solution optimizing the objective. These problems being NP-Hard, the solver takes exponential time in the size of the input to return a solution. In practice, we usually stop the solver and report the best solution found so far. This solution is usually suboptimal and, in the case of scheduling, causes delays or costs that could be avoided if the solver were able to find an optimal solution within the time limit, or simply a better solution. This justifies the development of faster solvers. The main goal of this research program is to speedup the solving process of constraint solvers. This will be done by exploring further a new filtering technique we introduced at IJCAI 2021 that improves filtering algorithms based on Lagrangian relaxation. A filtering algorithm prunes the search space by identifying choices that the solver could make to construct a solution but that lead to a contradiction with choices that were previously made. We proposed a new approach and tested it on the traveling salesperson problem and obtained a gain of 30% in resolution time that affected 93% of the instances of the benchmark compared to the best solution a constraint solver can offer. We want to reproduce this result with other constraints. Main objective: - To speedup the solving process of constraint solvers Sub-objectives: - To increase the amount of filtering provided by global constraints whose filtering algorithms are based on Lagrangian relaxation; - To propose new filtering algorithms based on Lagrangian relaxation; - To improve constraint propagation, i.e. the interaction between a set of constraints in order to increase the reduction of the search space. The constraints we propose to improve are used in a large variety of problems such as facility location problems, the traveling salesperson problem with or without time windows, scheduling problems with setup times, work shift scheduling, and scheduling with cumulative resources. We also plan to improve the filtering of the constraints based on a neural network. Such a constraint can force a solver to return a solution similar to the ones that were observed. We expect to improve the performance of constraint solvers, but as importantly, to form a new generation of researchers able to handle complex notions of optimization such as constraint programming and Lagrangian optimization. These researchers will evolve in an inclusive environment and achieve both fundamental research as presented in this Discovery Grant program but also applied research funded by other grants.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-05025
Name nom
Quimper, Claude-Guy
Department département
Informatique et génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
41000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
2950
Research subject group en
Applied mathematics
Research subject group fr
Applied mathematics
Research subject en
Mathématiques appliquées
Research subject fr
Mathématiques appliquées
Application title
Filtering Algorithms Based on Lagrangian Relaxation
Keyword
Combinatorial Optimization; Constraint Programming; Filtering Algorithms; Global Constraints; Operations Research
Application summary
Constraint programming emerged from artificial intelligence to become a paradigm for solving hard combinatorial problems such as scheduling problems. These problems are modeled with variables, constraints over these variables, and an objective function and are submitted to a constraint solver, a program able to return a solution optimizing the objective. These problems being NP-Hard, the solver takes exponential time in the size of the input to return a solution. In practice, we usually stop the solver and report the best solution found so far. This solution is usually suboptimal and, in the case of scheduling, causes delays or costs that could be avoided if the solver were able to find an optimal solution within the time limit, or simply a better solution. This justifies the development of faster solvers. The main goal of this research program is to speedup the solving process of constraint solvers. This will be done by exploring further a new filtering technique we introduced at IJCAI 2021 that improves filtering algorithms based on Lagrangian relaxation. A filtering algorithm prunes the search space by identifying choices that the solver could make to construct a solution but that lead to a contradiction with choices that were previously made. We proposed a new approach and tested it on the traveling salesperson problem and obtained a gain of 30% in resolution time that affected 93% of the instances of the benchmark compared to the best solution a constraint solver can offer. We want to reproduce this result with other constraints. Main objective: - To speedup the solving process of constraint solvers Sub-objectives: - To increase the amount of filtering provided by global constraints whose filtering algorithms are based on Lagrangian relaxation; - To propose new filtering algorithms based on Lagrangian relaxation; - To improve constraint propagation, i.e. the interaction between a set of constraints in order to increase the reduction of the search space. The constraints we propose to improve are used in a large variety of problems such as facility location problems, the traveling salesperson problem with or without time windows, scheduling problems with setup times, work shift scheduling, and scheduling with cumulative resources. We also plan to improve the filtering of the constraints based on a neural network. Such a constraint can force a solver to return a solution similar to the ones that were observed. We expect to improve the performance of constraint solvers, but as importantly, to form a new generation of researchers able to handle complex notions of optimization such as constraint programming and Lagrangian optimization. These researchers will evolve in an inclusive environment and achieve both fundamental research as presented in this Discovery Grant program but also applied research funded by other grants.