Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern
Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern
复制标题
对称性破缺是隐含约束的前奏：约束建模模式
DOI：
10.1007/978-3-642-37198-1_14
复制
发表时间：
2004
期刊：
影响因子：
4.8
通讯作者：
Ian Miguel
中科院分区：
文献类型：
--
作者：
Alan M. Frisch;Christopher Jefferson;Ian Miguel
域约束编程可以用来解决广泛的问题，首先将问题建模为一组约束，这些约束了问题的解决方案，然后搜索满足约束的解决方案。专家经常用隐含的约束和打破模型对称性的约束来扩充模型。在建模过程中出现的一种模式，强调和展示在这里，是一些强大的隐含的约束条件，可以派生后，破坏性的约束条件已被添加。此外，替代的对称性破坏约束之间的选择通常通过考虑对称性破坏的量或与强制执行约束的开销相比所获得的修剪强度来进行。我们证明，选择还应考虑的强度隐含的约束来自对称性破缺的约束。我们还讨论了未来的自动化选择的破坏性约束和推导隐含的约束。
Finite-domain constraint programming can be used to solve a wide range of problems by first modelling the problem as a set of constraints that characterise the problem's solutions, then searching for solutions that satisfy the constraints. Experts often augment models with implied constraints and constraints that break symmetries in the model. An emerging pattern in the modelling process, highlighted and demonstrated here, is that some powerful implied constraints can be derived only after symmetry-breaking constraints have been added. Furthermore, the choice between alternative symmetry-breaking constraints is commonly made by considering either the amount of symmetry broken or the strength of pruning obtained in comparison with the overhead of enforcing the constraints. We demonstrate that the choice should also consider the strength of the implied constraints derivable from the symmetry breaking constraints. We also discuss future automation of the selection of symmetry-breaking constraints and the derivation of implied constraints.