用图重写自动优化约束模型，提升求解效率
Automating Reformulation of Essence Specifications via Graph Rewriting
- 基于图重写技术自动重构本质约束模型结构
- 在实例上实现求解性能提升，验证了方法有效性
- 适合需要自动化建模优化的约束求解研究者
为参数化问题类构建高效的约束模型，是后续快速求解该类实例的关键。然而事先难以判断候选模型中哪个实际表现最优。本文提出一个系统，利用图重写技术自动重构输入模型以提升性能。通过将工作置于Essence抽象约束规范语言中，可直接利用其高层变量类型结构触发重写规则。系统通过图程序2语言实现重写规则，并作用于输入规范的抽象语法树。我们展示了如何自动将重构后问题的解映射回原问题的解，用于验证与呈现。通过详细案例研究，证明了该系统的有效性。
原文摘要 · Abstract (English)
Formulating an effective constraint model of a parameterised problem class is crucial to the efficiency with which instances of the class can subsequently be solved. It is difficult to know beforehand which of a set of candidate models will perform best in practice. This paper presents a system that employs graph rewriting to reformulate an input model for improved performance automatically. By situating our work in the Essence abstract constraint specification language, we can use the structure in its high level variable types to trigger rewrites directly. We implement our system via rewrite rules expressed in the Graph Programs 2 language, applied to the abstract syntax tree of an input specification. We show how to automatically translate the solution of the reformulated problem into a solution of the original problem for verification and presentation. We demonstrate the efficacy of our system with a detailed case study.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。