一句话：提出模型驱动方法 SoGen，用 DSL PDL 建模组合问题，自动分析问题性质并合成高效专用求解器（C 程序）。
组合问题广泛存在，但通用约束求解器架构复杂、求解效率不高。本文提出模型驱动方法 SoGen：用户用领域特定语言 PDL 对组合问题建模，SoGen 自动分析搜索空间、取值边界、函数单调性、重叠子问题等性质，并据此合成问题专用的高效求解器算法，最终生成 C 程序作为求解器。PDL 的独特之处在于能创建通过动态规划搜索来求解约束的求解器。摘要未报告量化实验，主要贡献是从约束模型自动生成专用求解器。
Combinatorial problems (CPs) arise in many areas, and people use constraint solvers to automatically solve these problems. However, the state-of-the-art constraint solvers (e.g., Gecode and Chuffed) have overly complicated software architectures; they compute solutions inefficiently. This paper presents a novel and model-driven approach---SoGen---to synthesize efficient problem-specific solvers from constraint models. Namely, when users model a CP with our domain-specific language PDL (short for Problem Description Language), SoGen automatically analyzes various properties of the problem (e.g., search space, value boundaries, function monotonicity, and overlapping subproblems), synthesizes an efficient solver algorithm based on those properties, and generates a C program as the problem solver. PDL is unique because it can create solvers that resolve constraints via dynamic programming (DP) search.
DOI 原文 ·
@inproceedings{paperbot6443,
title = {Generating efficient solvers from constraint models},
author = {Shu Lin and Na Meng and Wenxin Li},
booktitle = {FSE},
year = {2021},
doi = {10.1145/3468264.3468566}
}