Grant: Discovery Grants Program - Individual
Université Laval
$41,000.00
Filtering Algorithms Based on Lagrangian Relaxation
EF 2024-25
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
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
2024
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
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
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
Filtering Algorithms Based on Lagrangian Relaxation
Keywords
constraint programming; global constraints; combinatorial optimization; filtering algorithms; 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.