arXiv:2608.15143cs.AI2026-08

一个工具能自动把约束问题转成多种求解器格式,省去手动重写。

Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy

  • 设计高层建模语言,支持逻辑与算术运算及全局约束。
  • 通过模块化流水线转换,支持五类求解器的自动适配。
  • 解决非线性项线性化和负表达式处理难题,提升求解效率。

约束求解是一种用于组合满足与优化问题的声明式方法。用户通过约束和决策变量描述问题,由通用求解器寻找解。不同求解技术对特定问题表现各异,因此针对同一应用尝试多种求解器很有价值。但各求解范式支持的约束类型和变量不同。本文目标是将高层约束满足与优化问题自动翻译为包括CP、SMT QF-LIA、ILP、PB和(Max)SAT在内的多种低层形式,实现无需手动重模即可比较不同求解技术。我们定义了一种包含逻辑与算术操作、以及全局约束的高层语言,并提出一个模块化框架,实现从该语言到各类求解器的转换。尽管部分转换已有文献描述,我们发现可通过模块化流水线实现,低层级范式复用高层转换。核心挑战包括任意子表达式的否定处理与避免引入辅助变量。此外,特别关注非线性算子在ILP、PB和SAT求解器中的线性化。该流水线已在开源的CPMpy库中实现并评估,结果显示模型在转换过程中显著变化,且对线性化进行优化对ILP与PB求解器至关重要。

原文摘要 · Abstract (English)

Constraint solving is a declarative approach for solving combinatorial satisfaction and optimization problems. The user specifies their problem through constraints and decision variables, and a generic solver is used to find a solution. Several constraint-solving technologies exist, and certain solvers perform well on certain problems. Therefore, it is useful to try different solvers given a particular application. However, each solving paradigm supports different types of constraints and decision variables. Our goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism, including CP, SMT QF-LIA, ILP, PB and (Max)SAT. This allows for comparing different solving technologies for a particular problem, without requiring a user to manually remodel it for each solving paradigm. We define a high-level language of logical and arithmetic operations, and useful additional functions and constraints, which are known as global constraints in the CP community. We then present a modular framework for transforming our high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers. While many transformations are partly described in the literature, we observe that they can be implemented through a modular waterfall of smaller components, where lower-level paradigms reuse the transformations of higher-level paradigms. Two recurring challenges are handling the negation of arbitrary subexpressions and avoiding the introduction of auxiliary variables. Additionally, we take special care linearizing non-linear operators for ILP, PB and SAT-solvers. The transformation waterfall is implemented and evaluated in the open-source CPMpy library. Our results show that constraint models significantly change throughout the transformations, and that optimizations to the linearization of constraints are essential for ILP and PB solvers.

约束求解自动转换CPMpy

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。