論文の概要: A Distance Metric for Mixed Integer Programming Instances

• arxiv url: http://arxiv.org/abs/2507.11063v1
• Date: Tue, 15 Jul 2025 07:55:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-16 19:46:03.023197
• Title: A Distance Metric for Mixed Integer Programming Instances
• Title（参考訳）: 混合整数プログラミングインスタンスの距離メトリック
• Authors: Gwen Maudet, Grégoire Danoy,
• Abstract要約: Mixed-integer linear programming (MILP)は、様々な現実世界の問題に対処するための強力なツールである。 既存の類似度メトリクスは、しばしばインスタンスクラスを識別する精度を欠いているか、ラベル付きデータに大きく依存している。 本稿では,その数学的定式化から直接導出したMILPインスタンスに対する最初の数学的距離測定について紹介する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: Mixed-integer linear programming (MILP)は、様々な現実世界の問題に対処する強力なツールであるが、インスタンスを比較するための明確な構造が欠けている。 信頼性の高い類似度メトリックは、インスタンス間の有意義な関係を確立し、インスタンスセットの不均一性をより効果的に評価し、特に機械学習が関与する場合に、解決者へのより良いガイダンスを提供することができる。 既存の類似度メトリクスは、しばしばインスタンスクラスを識別する精度を欠いているか、ラベル付きデータに大きく依存しているため、適用性と一般化が制限される。 このギャップを埋めるために,本論文では,その数学的定式化から直接導出したMILPインスタンスに対する最初の数学的距離測定について紹介する。 右辺、重み、変数をクラスに分類することにより、提案された計量は地球移動器の距離からインスピレーションを得て、制約比較のための重み付き分布のミスマッチを定量化する。 このアプローチは、インスタンスレベルの比較を可能にするために自然に拡張されます。 我々は,StrIPLIBデータセットを用いて,パラメータ設定下において,測定値の正確な変種と強欲な変種をそれぞれ評価した。 その結果、計量のすべての成分がクラス識別に寄与し、グリーディ版は正確な定式化に近い精度を達成し、約200倍高速であることがわかった。 特徴ベース、画像ベース、ニューラルネットワークモデルを含む最先端のベースラインと比較して、教師なしの手法は、すべての非学習アプローチを一貫して上回り、クラスやサブクラスのグループ化タスクにおける教師付き分類器のパフォーマンスに匹敵する。

関連論文リスト

• Statistical Uncertainty Quantification for Aggregate Performance Metrics in Machine Learning Benchmarks [0.0]
  複数のタスクにまたがって集約されたメトリクスの不確かさを定量化するために,統計的手法がいかに用いられるかを示す。 これらの技術は、全体的なパフォーマンスが劣っているにもかかわらず、特定のタスクに対する特定のモデルの優位性のような洞察を浮き彫りにする。
  論文  参考訳（メタデータ） (2025-01-08T02:17:34Z)
• Hyperspherical Classification with Dynamic Label-to-Prototype Assignment [5.978350039412277]
  トレーニング中に各プロトタイプに割り当てられたカテゴリを最適化する,シンプルで効果的な手法を提案する。 この最適化は、勾配降下とバイパルチドマッチングの逐次組み合わせを用いて解決する。 CIFAR-100では1.22%の精度で、ImageNet-200では2.15%の精度で競合他社よりも優れています。
  論文  参考訳（メタデータ） (2024-03-25T17:01:34Z)
• Unsupervised Estimation of Ensemble Accuracy [0.0]
  いくつかの分類器の結合力を推定する手法を提案する。 ラベルに依存しない「多様性」対策に重点を置く既存のアプローチとは異なる。 本手法は,一般的な大規模顔認証データセット上で実証する。
  論文  参考訳（メタデータ） (2023-11-18T02:31:36Z)
• Revisiting Evaluation Metrics for Semantic Segmentation: Optimization and Evaluation of Fine-grained Intersection over Union [113.20223082664681]
  そこで本研究では,mIoUsの微細化と,それに対応する最悪の指標を提案する。 これらのきめ細かいメトリクスは、大きなオブジェクトに対するバイアスの低減、よりリッチな統計情報、モデルとデータセット監査に関する貴重な洞察を提供する。 ベンチマークでは,1つの測定値に基づかないことの必要性を強調し,微細なmIoUsが大きな物体への偏りを減少させることを確認した。
  論文  参考訳（メタデータ） (2023-10-30T03:45:15Z)
• An Additive Instance-Wise Approach to Multi-class Model Interpretation [53.87578024052922]
  解釈可能な機械学習は、ブラックボックスシステムの特定の予測を駆動する要因に関する洞察を提供する。 既存の手法は主に、局所的な加法的あるいはインスタンス的なアプローチに従う説明的入力特徴の選択に重点を置いている。 本研究は,両手法の長所を生かし,複数の対象クラスに対する局所的な説明を同時に学習するためのグローバルフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-07-07T06:50:27Z)
• A Lagrangian Duality Approach to Active Learning [119.36233726867992]
  トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。 制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。 数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
  論文  参考訳（メタデータ） (2022-02-08T19:18:49Z)
• Leveraging Ensembles and Self-Supervised Learning for Fully-Unsupervised Person Re-Identification and Text Authorship Attribution [77.85461690214551]
  完全ラベル付きデータからの学習は、Person Re-IdentificationやText Authorship Attributionなどのマルチメディアフォレスト問題において困難である。 近年の自己教師型学習法は,基礎となるクラスに意味的差異が有る場合に,完全ラベル付きデータを扱う際に有効であることが示されている。 本研究では,異なるクラスからのサンプルが顕著に多様性を持っていない場合でも,ラベルのないデータから学習できるようにすることにより,個人再認識とテキストオーサシップの属性に対処する戦略を提案する。
  論文  参考訳（メタデータ） (2022-02-07T13:08:11Z)
• Deep Relational Metric Learning [84.95793654872399]
  本稿では,画像クラスタリングと検索のためのディープリレーショナルメトリック学習フレームワークを提案する。 我々は、クラス間分布とクラス内分布の両方をモデル化するために、異なる側面から画像を特徴付ける特徴のアンサンブルを学ぶ。 広く使われているCUB-200-2011、Cars196、Stanford Online Productsデータセットの実験は、我々のフレームワークが既存の深層学習方法を改善し、非常に競争力のある結果をもたらすことを示した。
  論文  参考訳（メタデータ） (2021-08-23T09:31:18Z)
• Meta-Generating Deep Attentive Metric for Few-shot Classification [53.07108067253006]
  本稿では,新しい数ショット学習タスクのための特定のメトリックを生成するための,新しい深度メタジェネレーション手法を提案する。 本研究では,各タスクの識別基準を生成するのに十分なフレキシブルな3層深い注意ネットワークを用いて,メトリクスを構造化する。 特に挑戦的なケースでは、最先端の競合他社よりも驚くほどパフォーマンスが向上しています。
  論文  参考訳（メタデータ） (2020-12-03T02:07:43Z)
• Positive semidefinite support vector regression metric learning [0.0]
  これらのシナリオにおけるメートル法学習問題に対処するためにRAMLフレームワークが提案されている。 計量学習に必要な正の半定距離メートル法を学習することはできない。 弱さを克服するために2つのメソドを提案する。
  論文  参考訳（メタデータ） (2020-08-18T04:45:59Z)
• Unsupervised Feature Learning by Cross-Level Instance-Group Discrimination [68.83098015578874]
  我々は、インスタンスグループ化ではなく、クロスレベルな識別によって、インスタンス間の類似性を対照的な学習に統合する。 CLDは、教師なし学習を、自然データや現実世界のアプリケーションに効果的に近づける。 セルフスーパービジョン、セミスーパービジョン、トランスファーラーニングベンチマークに関する新たな最先端技術は、報告されたすべてのパフォーマンスでMoCo v2とSimCLRを上回っている。
  論文  参考訳（メタデータ） (2020-08-09T21:13:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。