Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
本文介绍了 CPMpy，这是一个模块化的开源框架，它能将高层有限域整数约束模型转换为各种低层求解形式（CP、SMT、ILP、PB 和 SAT），从而在无需手动重构模型的情况下，实现对不同求解技术的轻松比较。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在人工智能的广阔领域中，存在着一个被称为“建模并求解”（model-and-solve）的持久挑战。想象一个人正在组织一场复杂的活动，例如一场拥有数百名演讲者、多个房间和时间段的会议。他们并不会编写一个逐步执行的计算机程序来制定日程表，而是写下一组规则：“演讲者 A 不能在房间 B 发言”、“房间 C 必须在下午 2 点前使用”以及“演讲者 D 必须在演讲者 E 之后发言”。这组规则被称为约束模型（constraint model）。它是一种用人类可以理解的语言编写的高层问题描述。计算机的任务则是接收这些规则，并找到一个能同时满足所有规则的解。
困难之处在于，并没有一种单一的计算机程序能够擅长解决所有类型的规则。有些程序非常擅长处理逻辑上的“如果-那么”语句，而另一些则更擅长算术计算或管理大型可能性列表。研究人员已经构建了许多不同类型的这类求解程序，每种程序都有其自身的优势和劣势。然而，一个主要的障碍在于：为一种类型的求解器编写的问题通常无法被另一种求解器理解。为了使用不同的求解器，人类专家通常必须手动将整套规则重新改写为一种新的格式，这是一个乏味且容易出错的过程，限制了比较哪种工具最适合特定任务的能力。
鲁汶大学（KU Leuven）及其他机构的研究团队开发了一种解决这一翻译问题的方案。他们创建了一个名为 CPMpy 的软件库，它充当了这些约束模型的通用翻译器。他们的工作重点是将使用标准数学和逻辑规则编写的高层问题描述，自动转换为五种不同类型的求解技术所需的特定语言。这些技术涵盖了从专门处理复杂逻辑谜题的约束规划求解器，到擅长优化问题的整数线性规划求解器，甚至包括旨在检查逻辑陈述真伪的 SAT 求解器。研究人员不仅构建了一个翻译器，还构建了一个模块化的流水线，其中转换过程的每一步都是一个独立的、可重用的组件。这使得系统可以剥离特定求解器无法处理的复杂特征，并将其替换为该求解器可以理解的简单等效规则。
他们方法的核心是一个“瀑布式”的转换过程。当一个模型进入系统时，它首先会经过安全检查，以确保任何数学运算（如除法）对于所有可能的值都是有定义的。如果可能出现除以零的情况，系统会添加一个保护机制以防止发生。接着，系统会移除隐藏在复杂表达式深处的“非”（not）运算符，将其向下推进，直到它们仅适用于简单的变量。这简化了逻辑结构。随后，系统会将“全局约束”（global constraints）——即像“所有这些人必须有不同的日程安排”这样强大的高层规则——分解为更基础的构建模块，以便让更简单的求解器进行处理。
随着模型在流水线中向下移动，它会被“扁平化”。复杂的嵌套表达式会被简单的变量所取代，系统会跟踪这些替换过程以避免创建重复变量。这一步至关重要，因为许多求解器无法处理一个规则嵌套在另一个规则之内的情形。对于仅理解线性方程的求解器，系统会执行一种称为“线性化”（linearization）的过程。它将逻辑规则和不等式转换为直线方程。最后，对于仅处理真/假变量的求解器，系统会将每个整数编码为一系列布尔开关。在整个过程中，系统会小心地保持原始问题的精确含义。它确保如果原始高层模型存在解，那么翻译后的低层模型也必然存在解，反之亦然。
为了测试他们的系统，研究人员从一项主要的国际竞赛中提取了 250 个真实的优化问题。他们通过这个转换流水线运行这些问题，并将结果输入到三种不同类型的求解器中：一种领先的整数线性规划求解器、一种伪布尔（pseudo-boolean）求解器，以及一种最大可满足性（maximum satisfiability）求解器。他们测量了每个求解器找到最佳答案所需的时间。结果显示，转换过程显著改变了模型的结构。随着复杂的规则被分解为最简单的形式，规则和变量的数量往往会剧烈增加。然而，这种规模的扩张是使问题能被不同求解器理解所必需的。
研究还表明，模型的转换方式对性能有着重大影响。对于整数线性规划求解器，使用专门的方法来分解复杂规则可以缩短求解时间。对于其他求解器，影响则更为微妙。研究人员发现，对于某些求解器，标准转换效果最好；而对于另一些求解器，将数字视为简单真/假开关的激进转换则更为优越。他们发现，并非“一劳永逸”的方法行之有效；最佳的转换策略完全取决于所使用的特定求解器。事实上，对于某种类型的求解器，使用另一种类型最有效的转换方式反而会导致求解过程变慢。这凸显了拥有一个能够根据目标工具调整转换策略的灵活系统的必要性。
研究人员得出结论，他们的模块化方法成功弥合了高层问题建模与低层求解技术之间的鸿沟。通过自动化转换，他们允许用户编写一次问题，然后将其应用于多种不同的求解引擎进行测试，而无需手动重写。这种能力使得直接比较哪种技术最适合特定应用成为可能。虽然转换过程不可避免地增加了问题模型的规模，但利用不同求解器优势的能力远超这一成本。这项工作表明，借助正确的转换工具，多样化的约束求解世界可以变得触手可及且具有可比性，从而帮助研究人员和从业者找到解决复杂组合问题的最有效方案。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。