Automated Symmetry Breaking and Model Selection in Conjure
Automated Symmetry Breaking and Model Selection in Conjure
复制标题
Conjure 中的自动对称破缺和模型选择
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Peter William Nightingale
中科院分区：
文献类型：
--
作者：
Ozgur Akgun;Alan M. Frisch;Ian P. Gent;B. Hussain;Christopher Jefferson;Lars Kotthoff;Ian Miguel;Peter William Nightingale
约束建模被广泛认为是将约束求解应用于感兴趣的问题的关键瓶颈。CONJURE自动约束建模系统通过从用Essence语言编写的问题规范中自动细化约束模型来解决这个问题。ESSENCE提供了熟悉的数学概念，如嵌套到任何深度的集合、函数和关系。到目前为止，Conjure已经能够为给定的规范生成一组可选择的模型内核（即没有高级特性，如对称破缺或隐含约束）。本文的第一个贡献是在建模过程中引入了一种方法，通过该方法，CONJURE可以打破模型中的对称性。这适用于问题类级别，而不仅仅是单个实例，并且在制定模型之后不需要昂贵的检测步骤。这使得CONJURE能够产生更高质量的模型集。《CONJURE》的另一个限制是缺少一种机制去选择它所产生的模型。本文的第二个贡献是提出了两个这样的机制，允许自动选择有效的模型。
Constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. The CONJURE automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the Essence language. ESSENCE provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, Conjure has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. The first contribution of this paper is a method by which CONJURE can break symmetry in a model as it is introduced by the modelling process. This works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. This allows CONJURE to produce a higher quality set of models. A further limitation of CONJURE has been the lack of a mechanism to select among the models it produces. The second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Rendl Andrea
通讯作者：
Rendl Andrea