# A Distance Metric for Mixed Integer Programming Instances

arXiv: https://arxiv.org/abs/2507.11063 · HTML: https://mlsanity.com/paper/2507.11063/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 15 Jul 2025.

## Builds on (most cited first, 11 of 11)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Learning To Dive In Branch And Bound](https://mlsanity.com/paper/2301.09943/) (2023)
- [Learning Cuts via Enumeration Oracles](https://mlsanity.com/paper/2305.12197/) (2023)
- [Search Strategy Generation for Branch and Bound Using Genetic Programming](https://mlsanity.com/paper/2412.09444/) (2024)

## Abstract (arXiv)

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.