arXiv:2502.14760v1 宣告类型: 新 摘要: 在组合优化中，识别等价表示是基础问题之一，这可以导致更有效的求解策略，并深入理解问题的计算复杂性。随着优化协程（优化助手系统）的普及——这些系统能够从自然语言描述中生成问题表示——自动识别表示等价性的需求日益增长。然而，现有的表示等价性验证方法缺乏坚实的基础，依赖于简单的启发式方法，这些方法不足以进行严格的验证。受Karp归约的启发，本文提出了一种准Karp等价性形式准则，基于决策变量之间的映射来确定两个优化表示是否等价。我们提出了EquivaMap框架，利用大规模语言模型自动发现这种映射，从而实现可扩展且可靠的等价性验证。为了评估我们的方法，我们构建了首个开源的等价优化表示数据集，该数据集通过在现有表示上应用添加松弛变量或有效不等式等变换生成。实验证明，EquivaMap 显著优于现有方法，在正确识别表示等价性方面取得了重大进步。