标题： 一种混合整数规划实例的距离度量 显示英文标题

标题： A Distance Metric for Mixed Integer Programming Instances

摘要： 混合整数线性规划（MILP）是一种用于解决各种现实问题的强大工具，但它缺乏用于比较实例的清晰结构。 一个可靠的相似性度量可以建立实例之间的有意义关系，从而更有效地评估实例集的异质性，并为求解器提供更好的指导，特别是在涉及机器学习时。 现有的相似性度量通常在识别实例类方面不够精确，或者严重依赖标记数据，这限制了它们的适用性和泛化能力。 为了弥补这一差距，本文介绍了第一个针对MILP实例的数学距离度量，该度量直接来源于其数学公式。 通过将右侧、权重和变量离散化为类别，所提出的度量受到地球移动距离的启发，以量化约束比较中的权重-变量分布不匹配。 这种方法自然地扩展以实现实例级比较。 我们在各种参数设置下评估了我们度量的精确版本和贪心版本，使用了StrIPLIB数据集。 结果表明，度量的所有组件都对类识别有贡献，而贪心版本在准确性上几乎与精确公式相同，同时速度快近200倍。 与最先进的基线方法相比，包括基于特征、基于图像和神经网络的模型，我们的无监督方法在类和子类分组任务中始终优于所有非学习方法，并与监督分类器的性能相当。 显示英文摘要

摘要： Mixed-integer linear programming (MILP) is a powerful tool for addressing a wide range of real-world problems, but it lacks a clear structure for comparing instances. A reliable similarity metric could establish meaningful relationships between instances, enabling more effective evaluation of instance set heterogeneity and providing better guidance to solvers, particularly when machine learning is involved. Existing similarity metrics often lack precision in identifying instance classes or rely heavily on labeled data, which limits their applicability and generalization. To bridge this gap, this paper introduces the first mathematical distance metric for MILP instances, derived directly from their mathematical formulations. By discretizing right-hand sides, weights, and variables into classes, the proposed metric draws inspiration from the Earth mover's distance to quantify mismatches in weight-variable distributions for constraint comparisons. This approach naturally extends to enable instance-level comparisons. We evaluate both an exact and a greedy variant of our metric under various parameter settings, using the StrIPLIB dataset. Results show that all components of the metric contribute to class identification, and that the greedy version achieves accuracy nearly identical to the exact formulation while being nearly 200 times faster. Compared to state-of-the-art baselines, including feature-based, image-based, and neural network models, our unsupervised method consistently outperforms all non-learned approaches and rivals the performance of a supervised classifier on class and subclass grouping tasks.