Filtering Algorithms Based on Lagrangian Relaxation

基于拉格朗日松弛的滤波算法

• 批准号: RGPIN-2022-05025
• 负责人: Quimper, ClaudeGuy
• 金额: $ 2.99万
• 依托单位: Université Laval
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=757343
• 关键词: Filtering; Algorithms; Based; 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.

约束编程从人工智能中产生，成为解决诸如调度问题等困难组合问题的范例。这些问题用变量、对这些变量的约束和目标函数建模，并提交给约束求解器，该程序能够返回优化目标的解决方案。这些问题是NP难的，求解器需要输入大小的指数时间来返回解决方案。在实践中，我们通常会停止求解程序并报告到目前为止找到的最佳解决方案。这种解决方案通常是次优的，并且在调度的情况下，如果求解器能够在时间限制内找到最优解决方案，或者仅仅是更好的解决方案，则可以避免延迟或成本。这证明了开发更快的求解器的合理性。本研究计画的主要目标是加速约束求解器的求解过程。这将通过进一步探索我们在IJCAI 2021上引入的新过滤技术来实现，该技术改进了基于拉格朗日松弛的过滤算法。过滤算法通过识别求解器可以做出的选择来修剪搜索空间，以构造解决方案，但这些选择会导致与先前做出的选择相矛盾。我们提出了一种新的方法，并在旅行销售员问题上进行了测试，与约束求解器可以提供的最佳解决方案相比，解决时间增加了30%，影响了基准测试的93%的实例。我们希望在其他约束条件下重现这个结果。主要目标：- 加速约束求解器的求解过程子目标：-增加由全局约束提供的过滤量，其过滤算法基于拉格朗日松弛; -提出基于拉格朗日松弛的新的过滤算法; -改进约束传播，即一组约束之间的相互作用，以便增加搜索空间的减少。我们提出的约束条件，以改善被用于各种各样的问题，如设施选址问题，旅行售货员的问题，有或没有时间窗口，调度问题的设置时间，轮班调度，调度与累积资源。我们还计划改进基于神经网络的约束过滤。这样的约束可以强制求解器返回与观察到的解类似的解。我们希望提高约束求解器的性能，但同样重要的是，形成新一代的研究人员能够处理复杂的优化概念，如约束编程和拉格朗日优化。这些研究人员将在一个包容的环境中发展，并实现本发现补助金计划中提出的基础研究，以及其他赠款资助的应用研究。