Filtering Algorithms Based on Lagrangian Relaxation

点击翻译按钮获取中文摘要

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.