约束获取需要更好的基准测试

# 约束获取需要更好的基准测试 来源：https://arxiv.org/html/2605.26279 \\hideLIPIcs 波兹南工业大学计算科学研究所，Piotrowo 2, 波兹南，波兰 rstachowiak@cs\.put\.poznan\.plhttps://orcid\.org/0009-0002-7978-900X 波兹南工业大学计算科学研究所，Piotrowo 2, 波兹南，波兰 tpawlak@cs\.put\.poznan\.plhttps://orcid\.org/0000-0002-8353-0562 \\CopyrightRafał Stachowiak and Tomasz P\. Pawlak \\ccsdesc\[100\]Theory of computation Mathematical optimization \\ccsdesc\[100\]Applied computing Operations research \\relatedversion\\supplementhttps://github.com/MPMMine/MPMMine \\funding本研究全部或部分由波兰国家科学中心资助，资助编号为2023/50/E/ST6/00237。为开放获取目的，作者已将CC-BY公共版权许可应用于因本投稿产生的任何作者接受稿件（AAM）版本。\\EventEditorsFill Me With Names \\EventNoEds2 \\EventLongTitle第32届约束编程原理与实践国际会议（CP 2026） \\EventShortTitleCP 2026 \\EventAcronymCP \\EventYear2026 \\EventDate2026年7月20–23日 \\EventLocation葡萄牙里斯本 \\EventLogo \\SeriesVolume1 \\ArticleNo1 ###### 摘要 约束获取（CA）及相关的基于领域知识工件验证和增强数学规划（MP）模型的研究，目前受限于不充分的基准测试集。这一缺陷阻碍了可复现性和跨研究可比性，从而减缓了CA方法的成熟。现有基准测试是为求解器评估而非评估CA算法而设计的。它们组织松散，对各个问题的处理不一致，并且遗漏了CA方法所需的领域知识工件。本文介绍了MPMMine，一个旨在使用多种领域知识工件评估发现、验证和增强MP模型的算法的基准测试套件。MPMMine的指导原则是一致性、标准化、完整性、可扩展性、开放性和版本控制。它采用统一结构并依赖开放格式：MiniZinc、CommonMark和JSON。它为每个问题提供多个模型、每个模型提供数十个实例，以及每个实例提供数千个整数域和连续域的解和非解，同时附带自然语言描述以支持文本到模型的方法。 ###### 关键词：建模与建模语言、运筹学与数学优化、测试、约束获取、基准测试、线性规划 ## 1 引言 ### 1.1 背景 数学规划（MP）模型\[williams2013model\]是一种表达计算问题的形式体系：变量表示待确定的未知量，约束捕捉它们之间的关系，目标函数评估候选解。高级MP语言，如MiniZinc\[minizinc1\]，通过支持参数、数据结构以及基于量词、集合代数和全局约束的简洁构造（替代冗长的低级方程列表），进一步扩展了这一框架。设计一个高质量的MP模型可能需要大量时间——对于包含数千个变量和约束的现实实例，通常需要数周时间。*约束获取*（CA）\[bessiere2017constraint,10.1613/jair.1.14752,Menguy2025,10.1145/3205455.3205480,Pawlak2021,Tsouros2020\]通过提供从领域知识工件（主要是示例解）中发现MP模型的算法来应对这一挑战。因此，CA支持专家从现有数据中推导MP模型。同时，CA自然适应于更广泛的场景：不仅发现新的MP模型，还使用领域知识工件检查一致性并增强现有模型。为了将CA与这一更广泛的视角区分开来，我们引入总称术语*MP模型挖掘*（MPMM），它涵盖了基于领域知识进行MP模型发现、一致性检查和增强的所有任务。 关于MPMM的现有文献十分丰富\[STACHOWIAK2026100905\]，反映了活跃的研究态势。尽管如此，大多数贡献仍停留在基础研究层面，未超越技术就绪等级3。即便是这些基础研究也受到若干问题的阻碍，延缓或阻止了进一步进展： 1. 1.*不可复现的实验*——实验方案经常遗漏关键细节；例如：训练和测试解是如何生成的？实例的分布是怎样的？使用了什么约束基数界限？ 2. 2.*无法比较的结果*——使用自定义实验设置导致结果难以比较；例如：论文之间报告的性能差异是源于真正的算法进步，还是源于不同的实验方法？ 3. 3.*非标准基准测试*——计算问题以多种变体出现，每种变体允许不同的MP编码；例如：所选的问题编码是否经过定制以有利于被评估的算法？特定基准测试集是基于什么理由选择的？ 4. 4.*有限的实例*——评估单个问题实例的研究未能反映算法在整个问题类别上的真实性能；例如：随着问题实例规模的增大，算法如何扩展？ 5. 5.*连续和混合问题的稀缺性*——尽管连续变量问题具有实际相关性，但在MPMM研究中常被忽视；例如：不精确的变量值或参数是如何处理的？容差水平是如何设置的？ 我们认为这些共同的困难主要源于缺乏专门的MPMM研究基础设施。现有的基准测试套件，如CSPLib\[csplib\]、MiniZinc挑战赛\[minizinc2\]和MIPLIB\[MIPLIB\]，是为评估求解器而非MPMM方法而创建的。此外，这些基准测试缺乏严格标准化：实例在文件组织上不同，使用异构建模语言（例如，MiniZinc\[minizinc1\]、OPL\[OPL\]、Essence\[essence\]、CPMpy\[cpmpy\]、MPS\[gurobi\]），并且常常省略或不一致地存储领域知识工件（例如，解、参数、描述）。因此，MPMM研究通常采用临时实验设置，其中缺失的工件（如示例解）是通过很少记录的定制程序生成的。 ### 1.2 贡献 我们提出了*MPMMine*，一个旨在评估MPMM问题全谱（发现、一致性检查和增强）上算法性能的基准测试数据集。MPMMine的开发遵循六项关键原则——*一致性*、*标准化*、*完整性*、*可扩展性*、*开放性*和*版本控制*——这些原则在第3.1节（https://arxiv.org/html/2605.26279#S3.SS1）中详述。MPMMine目前包含16个问题，包括组合型、连续型和混合型，并且还在持续增长。每个问题关联数十个实例、自然语言描述以及每个实例数千个解和非解。所有数据均通过记录完善的协议生成，有助于实验的可复现性，并通过共享训练/测试集使不同研究之间能够公平比较。基准测试格式是标准化的，因此可以在无需修改现有代码的情况下使用更大的问题集合。对于每个MP模型，实例覆盖了多种规模和复杂度，有助于评估可扩展性。 ## 2 相关工作 几乎所有MP模型的基准测试集合都是为评估求解器而开发的，而非评估使用领域知识工件挖掘MP模型的算法。在此，我们强调在MPMM相关工作中最常见的数据集（如\[STACHOWIAK2026100905\]所总结）的缺陷，并将它们与MPMMine进行比较。 *CSPLib*\[csplib\]是一个经过整理的组合问题集合，主要以约束编程模型\[essentialsOfConstraintProgramming\]的形式表述。然而，它缺乏标准化：不同问题的目录布局不同，补充性工件的性质和质量变化很大，大多数实例既不提供代表性解也不提供反例。与MPMMine不同，使用CSPLib需要手动将每个问题调整到目标实验设置中，例如，将模型重写为所需形式并构建训练示例。 *MiniZinc挑战赛*\[minizinc2\]虽然提供了结构良好的MiniZinc模型和实例，但仅限于组合问题，并且主要设计用于评估求解器。与MPMMine不同，它既不提供解/非解，也不提供自然语言描述。 *MIPLIB*\[MIPLIB\]将范围扩展到连续和混合整数优化问题；然而，它针对求解器性能评估，并以各种低层格式（MPS, LP）存储模型，附带的元数据有限，导致标准化程度低，并且与MPMMine相反，它缺少评估MPMM算法所需的必要工件。 其他资源也面临类似限制：*Netlib*\[netlib\]提供了一个经典但过时的线性规划（LP）模型集合，用于求解器测试；*RLFAP*数据集\[rlfap\]以领域特定格式提供无线电链路频率分配实例；*NL4Opt*\[nl4opt\]专注于从自然语言文本中提取优化公式，但不提供结构化的MP模型、实例或解集。 总之，现有基准测试缺乏一致的结构和元数据，仅覆盖了狭窄的问题类别，并且遗漏了系统评估MPMM算法所必需的领域知识工件（示例、描述）。MPMMine通过一个专门构建、结构一致且可扩展的数据集来解决这些不足。 ## 3 MPMMine：MP模型挖掘的标准化基准测试 表1：MPMMine中当前实现的问题。 MPMMine的主要目标是为利用领域知识发现和维护MP模型的多样化AI任务提供一个标准化的基准测试集合。此处，领域知识指任何指定计算问题的信息，包括文本描述、正式文档、方程式、符号集、示例解和反例解、现有MP模型、不可约不一致子系统及其任意组合。表1（https://arxiv.org/html/2605.26279#S3.T1）总结了MPMMine当前包含的问题。第3.1节（https://arxiv.org/html/2605.26279#S3.SS1）介绍了行为准则。第3.2节（https://arxiv.org/html/2605.26279#S3.SS2）概述了获取工件的程序。 ### 3.1 行为准则 我们严格遵守以下六条规则来构建MPMMine。 ##### 规则1：一致性 所有问题的目录结构一致。所有问题、模型、数据和元数据共享相同的文件结构和文件格式。数据集在`problems`根目录下组织为四层层次结构，以适应不同的建模方法和具体数据实例，如下所示： 1. 1.**问题**：每个问题在`problems`目录下拥有一个独立子目录。 2. 2.**MP模型**：每个问题包含一个或多个对应于不同编码和公式的MP模型子目录。 3. 3.**抽象描述和实例**：每个模型有两个子目录：`descriptions`对应于独立于实例（即没有具体值）的问题描述，以及`instances`包含带有抽象模型参数具体值的数据文件。 4. 4.**工件**：此层级存储与特定实例相关的工件，包括解、非解和特定于实例的文本描述。 文件树结构如下所示，其中`[R]`标记表示必需文件： ``` problems/ P000 problem name/ manifest.json [R] references.bib [R] models/ M000/ model.mzn [R] descriptions/ D000 description.en.md instances/ I000 instance name/ instance.dzn [R] descriptions/ D000 description.en.md solutions/ S000000 sol.dzn non solutions/ N000000 non_sol.dzn ``` 该数据集采用结构化的层次化标识符，确保每个文件都被唯一引用。层级特定ID由与文件类型相关的单字母前缀和三位或六位唯一代码组成，例如`P003`代表问题，`M002`代表模型等。通过连接各层级的ID，生成一个全局ID，例如`MPMMine-P003M002I003S00055`精确定位到“P003 模板设计”问题的第三个实例中第二个模型的第55个解。`MPMMine-`前缀作为外部引用的命名空间。不完整的ID允许引用层次结构的更高级别。 每个问题包含一个`manifest.json`文件，为人类读者和机器提供结构化元数据。顶层属性定义如下： - •`id` – 问题ID，与问题目录名称一致， - •`name` – 描述性标题， - •`tags` – 用于索引的问题特定键值对；取自维基数据\[wikidata\]， - •`features` – 布尔标志，指示高级特征，如约束、目标函数、是否属于优化或可满足性问题，以及变量类型， - •`alternative_ids` – 映射到其他基准测试数据集中的相关问题， - •`references` – 类似于BibTeX的论文元数据， - •`links` – 相关资源的URL。 `references.bib`是相关文档的即用型BibTeX定义。它包含与`manifest.json`的`references`部分相同条目。 每个`models`目录至少包含一个子目录，其中包含引用MiniZinc模型的`.mzn`格式文件。这些模型是独立于实例的，通过抽象参数而非硬编码值来定义问题的逻辑。为了支持文本到模型的基准测试，每个模型在`descriptions`子目录中至少包含一个英文描述。这些描述也使用符号或自然语言而非具体数字，并针对其相应MP模型的逻辑进行调整。包含问题完整数学公式的描述在文件名中明确使用`formal`单词标记。其他语言的描述是可选的（由语言代码后缀指示）。 每个MP模型在`instances`目录中包含一个或多个具体实例，遵循`I000 instance_name`命名约定。`instance.dzn`文件提供填充模型抽象参数所需的具体数据值。虽然实例通常是可行的，但数据集也包含没有解的不满足实例。这些实例通过在`.dzn`文件的第一行放置`% UNSATISFIABLE`标记来明确标记，以确保在基准测试期间正确处理。 每个实例由位于子目录中的领域知识工件补充： - •`descriptions` – 符号设置为具体值的实例级描述。 - •`solutions` – 唯一解（例如，`S000000 sol.dzn`）；目标是每个实例10,000个解；但对于解空间较小或计算困难的实例，可能提供较少；对于不满足实例，此目录被省略。 - •`non solutions` – 唯一非解（例如，`N000000 non_sol.dzn`）；默认数量为10,000，但对于无约束问题，此目录被排除。有关这些文件如何创建的详细信息，请参阅第3.2节（https://arxiv.org/html/2605.26279#S3.SS2）。 ##### 规则2：标准化 该数据集仅依赖开放标准以确保互操作性和可访问性：MiniZinc\[minizinc1\]用于MP模型，CommonMark\[