论文标题
半检查传播器
Half-checking propagators
论文作者
论文摘要
繁殖者是约束编程成功的核心，即签约功能删除值证明不适合给定约束的任何解决方案。对于许多不同的约束，文献包含许多传播算法，所有这些繁殖算法共有的是正确性的概念：只能删除无需解决各自约束的值的值。在本文中，引入了半检查繁殖者，唯一的要求是（传播器）确定的解决方案是实际解决方案（对相应的约束），并且传播器正在签约。特别是，半检查繁殖器可能会删除导致不完整解决过程的解决方案，但是随着（良好）解决方案的上涨速度可能会更快。可以通过将半检查传播器作为投资组合解决过程中的一个组件来获得总体完整性。与当前可用的相比，半检查传播器在设计传播算法时开放了多种技术。 介绍了用于半检查繁殖器的正式模型，以及有关如何在约束编程系统中支持此类繁殖器的详细说明。引入了三个用于创建半检查繁殖算法的一般方向，并用于设计新的半检查传播器作为成本电路约束作为示例。新的繁殖器是在Gecode系统中实现的。
Propagators are central to the success of constraint programming, that is contracting functions removing values proven not to be in any solution of a given constraint. The literature contains numerous propagation algorithms, for many different constraints, and common to all these propagation algorithms is the notion of correctness: only values that appear in no solution to the respective constraint may be removed. In this paper half-checking propagators are introduced, for which the only requirements are that identified solutions (by the propagators) are actual solutions (to the corresponding constraints), and that the propagators are contracting. In particular, a half-checking propagator may remove solutions resulting in an incomplete solving process, but with the upside that (good) solutions may be found faster. Overall completeness can be obtained by running half-checking propagators as one component in a portfolio solving process. Half-checking propagators opens up a wider variety of techniques to be used when designing propagation algorithms, compared to what is currently available. A formal model for half-checking propagators is introduced, together with a detailed description of how to support such propagators in a constraint programming system. Three general directions for creating half-checking propagation algorithms are introduced, and used for designing new half-checking propagators for the cost-circuit constraint as examples. The new propagators are implemented in the Gecode system.
