Conjure: Automatic Generation of Constraint Models from Problem Specifications
Conjure: Automatic Generation of Constraint Models from Problem Specifications
复制标题
DOI：
10.1016/j.artint.2022.103751
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Özgür Akgün;Alan M. Frisch;Ian P. Gent;Christopher Jefferson;Ian Miguel;Peter William Nightingale
中科院分区：
文献类型：
--
作者：
Özgür Akgün;Alan M. Frisch;Ian P. Gent;Christopher Jefferson;Ian Miguel;Peter William Nightingale
在解决组合问题时，问题的公式化或模型对求解器的效率至关重要。自动化的建模过程一直感兴趣，因为专业知识和时间需要产生一个给定问题的有效模型。我们描述了一种方法来自动产生约束模型，从一个问题的规范写在抽象的约束规范languageEssence。我们的方法是通过在每一步应用一个选定的细化规则，逐步将规范细化为一个具体的模型。任何非平凡的规范都可以通过多种方式进行细化，从而创建可供选择的模型空间。对称性的处理是自动建模的一个特别重要的方面。许多组合优化问题包含对称性，这可能导致冗余搜索。如果一个部分赋值被证明是无效的，那么如果我们考虑它的一个对称等价物，我们就是在浪费时间。一类特别重要的对称性是由约束建模过程引入的：建模对称性。我们展示了如何建模对称性可能会被自动打破，因为他们在细化过程中进入一个模型，避免了一个昂贵的对称性检测步骤模型formulation.Our的方法是在一个系统中实现的调用Conjure。我们比较的模型产生的共轭约束模型从文献中已知是有效的。我们的实证结果证实了Conjurecan成功地再现了文献中发现的42个基准问题的约束模型的内核。
When solving a combinatorial problem, the formulation ormodelof the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest because of the expertise and time required to produce an effective model of a given problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification languageEssence. Our approach is to incrementallyrefinethe specification into a concrete model by applying a chosenrefinement ruleat each step. Any non-trivial specification may be refined in multiple ways, creating a space of models to choose from.The handling of symmetries is a particularly important aspect of automated modelling. Many combinatorial optimisation problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: modelling symmetries. We show how modelling symmetries may be broken automatically as they enter a model during refinement, obviating the need for an expensive symmetry detection step following model formulation.Our approach is implemented in a system calledConjure. We compare the models produced byConjureto constraint models from the literature that are known to be effective. Our empirical results confirm thatConjurecan reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.