Filtering Algorithms Based on Lagrangian Relaxation

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

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.