Solving Satisfaction Problems Using Large-Neighbourhood Search
Solving Satisfaction Problems Using Large-Neighbourhood Search
复制标题
使用大邻域搜索解决满意度问题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Guido Tack
中科院分区：
文献类型：
--
作者：
Gustav Björdal;P. Flener;J. Pearson;Peter James Stuckey;Guido Tack
大型邻居搜索（LNS）改善了初始解决方案，因此它不适用于满意度问题。为了在约束编程（CP）框架中使用LNS来解决满意度问题，我们通常通过用惩罚功能限制来替换一些难以确定的约束。然后使用LNS将其罚款减少到零，从而满足了原始问题。但是，由于罚款很少引起传播，因此可以使性能差，因此不会推动每个CP搜索，并且通过扩展LNS搜索，直到很晚才满足替换的约束。我们的主要观察结果是，完全替换约束通常是过度杀伤，因为替换约束的传播器可能会执行一些传播而不会引起回溯。我们提出了一个非解放传播器的概念，该概念在引起回溯之前就归入了。我们表明，只要对现有CP求解器进行几次更改，就可以在不修改其代码的情况下进行非失败。实验评估表明，与仅受到惩罚相比，非灭绝传播器与惩罚结合使用时可以大大提高LNS性能。这使我们能够利用CP求解器中已经存在的许多复杂的繁殖者的功能，以便使用LNS解决硬满意度问题并找到初始解决方案，以难以满意的优化问题。
Large-neighbourhood search (LNS) improves an initial solution, hence it is not directly applicable to satisfaction problems. In order to use LNS in a constraint programming (CP) framework to solve satisfaction problems, we usually soften some hard-to-satisfy constraints by replacing them with penalty-function constraints. LNS is then used to reduce their penalty to zero, thus satisfying the original problem. However, this can give poor performance as the penalties rarely cause propagation and therefore do not drive each CP search, and by extension the LNS search, towards satisfying the replaced constraints until very late. Our key observation is that entirely replacing a constraint is often overkill, as the propagator for the replaced constraint could have performed some propagation without causing backtracking. We propose the notion of a non-failing propagator, which is subsumed just before causing a backtrack. We show that, by only making a few changes to an existing CP solver, any propagator can be made non-failing without modifying its code. Experimental evaluation shows that non-failing propagators, when used in conjunction with penalties, can greatly improve LNS performance compared to just having penalties. This allows us to leverage the power of the many sophisticated propagators that already exist in CP solvers, in order to use LNS for solving hard satisfaction problems and for finding initial solutions to hard-to-satisfy optimisation problems.