A Distance Metric for Mixed Integer Programming Instances

• URL: http://arxiv.org/abs/2507.11063v1
• Date: Tue, 15 Jul 2025 07:55:09 GMT
• Title: A Distance Metric for Mixed Integer Programming Instances
• Authors: Gwen Maudet, Grégoire Danoy,
• Abstract summary: Mixed-integer linear programming (MILP) is a powerful tool for addressing a wide range of real-world problems.<n>Existing similarity metrics often lack precision in identifying instance classes or rely heavily on labeled data.<n>This paper introduces the first mathematical distance metric for MILP instances, derived directly from their mathematical formulations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Statistical Uncertainty Quantification for Aggregate Performance Metrics in Machine Learning Benchmarks [0.0]
  We show how statistical methodology can be used for quantifying uncertainty in metrics that have been aggregated across multiple tasks.<n>These techniques reveal insights such as the dominance of a specific model for certain types of tasks despite an overall poor performance.
  arXiv  Detail & Related papers  (2025-01-08T02:17:34Z)
• Hyperspherical Classification with Dynamic Label-to-Prototype Assignment [5.978350039412277]
  We present a simple yet effective method to optimize the category assigned to each prototype during the training. We solve this optimization using a sequential combination of gradient descent and Bipartide matching. Our method outperforms its competitors by 1.22% accuracy on CIFAR-100, and 2.15% on ImageNet-200 using a metric space dimension half of the size of its competitors.
  arXiv  Detail & Related papers  (2024-03-25T17:01:34Z)
• Unsupervised Estimation of Ensemble Accuracy [0.0]
  We present a method for estimating the joint power of several classifiers. It differs from existing approaches which focus on "diversity" measures by not relying on labels. We demonstrate the method on popular large-scale face recognition datasets.
  arXiv  Detail & Related papers  (2023-11-18T02:31:36Z)
• Revisiting Evaluation Metrics for Semantic Segmentation: Optimization and Evaluation of Fine-grained Intersection over Union [113.20223082664681]
  We propose the use of fine-grained mIoUs along with corresponding worst-case metrics. These fine-grained metrics offer less bias towards large objects, richer statistical information, and valuable insights into model and dataset auditing. Our benchmark study highlights the necessity of not basing evaluations on a single metric and confirms that fine-grained mIoUs reduce the bias towards large objects.
  arXiv  Detail & Related papers  (2023-10-30T03:45:15Z)
• An Additive Instance-Wise Approach to Multi-class Model Interpretation [53.87578024052922]
  Interpretable machine learning offers insights into what factors drive a certain prediction of a black-box system. Existing methods mainly focus on selecting explanatory input features, which follow either locally additive or instance-wise approaches. This work exploits the strengths of both methods and proposes a global framework for learning local explanations simultaneously for multiple target classes.
  arXiv  Detail & Related papers  (2022-07-07T06:50:27Z)
• A Lagrangian Duality Approach to Active Learning [119.36233726867992]
  We consider the batch active learning problem, where only a subset of the training data is labeled. We formulate the learning problem using constrained optimization, where each constraint bounds the performance of the model on labeled samples. We show, via numerical experiments, that our proposed approach performs similarly to or better than state-of-the-art active learning methods.
  arXiv  Detail & Related papers  (2022-02-08T19:18:49Z)
• Leveraging Ensembles and Self-Supervised Learning for Fully-Unsupervised Person Re-Identification and Text Authorship Attribution [77.85461690214551]
  Learning from fully-unlabeled data is challenging in Multimedia Forensics problems, such as Person Re-Identification and Text Authorship Attribution. Recent self-supervised learning methods have shown to be effective when dealing with fully-unlabeled data in cases where the underlying classes have significant semantic differences. We propose a strategy to tackle Person Re-Identification and Text Authorship Attribution by enabling learning from unlabeled data even when samples from different classes are not prominently diverse.
  arXiv  Detail & Related papers  (2022-02-07T13:08:11Z)
• Deep Relational Metric Learning [84.95793654872399]
  This paper presents a deep relational metric learning framework for image clustering and retrieval. We learn an ensemble of features that characterizes an image from different aspects to model both interclass and intraclass distributions. Experiments on the widely-used CUB-200-2011, Cars196, and Stanford Online Products datasets demonstrate that our framework improves existing deep metric learning methods and achieves very competitive results.
  arXiv  Detail & Related papers  (2021-08-23T09:31:18Z)
• Meta-Generating Deep Attentive Metric for Few-shot Classification [53.07108067253006]
  We present a novel deep metric meta-generation method to generate a specific metric for a new few-shot learning task. In this study, we structure the metric using a three-layer deep attentive network that is flexible enough to produce a discriminative metric for each task. We gain surprisingly obvious performance improvement over state-of-the-art competitors, especially in the challenging cases.
  arXiv  Detail & Related papers  (2020-12-03T02:07:43Z)
• Positive semidefinite support vector regression metric learning [0.0]
  RAML framework is proposed to handle the metric learning problem in those scenarios. It can't learn positive semidefinite distance metric which is necessary in metric learning. We propose two methds to overcame the weakness.
  arXiv  Detail & Related papers  (2020-08-18T04:45:59Z)
• Unsupervised Feature Learning by Cross-Level Instance-Group Discrimination [68.83098015578874]
  We integrate between-instance similarity into contrastive learning, not directly by instance grouping, but by cross-level discrimination. CLD effectively brings unsupervised learning closer to natural data and real-world applications. New state-of-the-art on self-supervision, semi-supervision, and transfer learning benchmarks, and beats MoCo v2 and SimCLR on every reported performance.
  arXiv  Detail & Related papers  (2020-08-09T21:13:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.