論文の概要: When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming
- arxiv url: http://arxiv.org/abs/2610.12876v1
- Date: Fri, 09 Oct 2026 02:09:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.348955
- Title: When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming
- Title（参考訳）: 解答者がムードを得るとき:混合整数プログラミングにおけるパフォーマンス変数の定量化と予測
- Abstract要約: 混合整数計画法(MIP)は広く用いられているが、その性能は一見中立な摂動の下でも大きく異なる。
Weighted Variability Score (WVS)は、正規化ランタイムにおける分散、最終的な最適性ギャップ、LP、分岐とバウンドノードを集約する頑健なマルチコンポーネントメトリックである。
可変性は、安価な早期実行機能から体系的で部分的に予測可能であるため、プリエンプティブをチューニングし、新しいアルゴリズムを公平に評価するための基盤を置くための実用的なツールを提供する。
- 参考スコア（独自算出の注目度）: 3.6807551678197874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Mixed-integer programming (MIP) solvers are widely used, yet their performance can vary substantially even under seemingly neutral perturbations. Such variability complicates benchmarking, and the interpretation of computational studies. We introduce the Weighted Variability Score (WVS), a robust multi-component metric that aggregates dispersion in normalized runtime, final optimality gap, LP iterations, and branch-and-bound nodes across repeated runs. On a large subset of MIPLIB 2017 instances, each solved in 100 randomized runs under a four-hour limit, WVS reveals a right-skewed distribution with a substantial upper tail: many instances are essentially stable, but some exhibit large variability that is not explained by basic properties alone. Notably, this experiment proved optimality for the open instance 'neos-5045105-creuse' in two SCIP runs. Using static descriptors and root-level features, a tree-based predictor with a gated tail uplift achieves a mean absolute error of 0.058 and Spearman rank correlation of 0.65 on a sealed test split. Feature-importance analysis highlights root degeneracy, matrix structure, coefficient ranges, and presolve reductions as the main drivers of high WVS. Because variability is systematic and partially predictable from inexpensive early-run features, our findings offer a practical tool for preemptive tuning and lay a foundation for fairer evaluation of new algorithms.
- Abstract（参考訳）: 混合整数計画法(MIP)は広く用いられているが、その性能は一見中立な摂動の下でも大きく異なる。
このような変動性は、ベンチマークと計算研究の解釈を複雑にする。
Weighted Variability Score (WVS)は、正規化ランタイムにおける分散、最終的な最適性ギャップ、LPイテレーション、繰り返し実行における分岐とバウンドノードを集約する堅牢なマルチコンポーネントメトリックである。
MIPLIB 2017インスタンスの大規模なサブセットでは、それぞれが4時間制限で100個のランダム化された実行で解決された。
特に、この実験は2回のSCIP実行におけるオープンインスタンス'neos-5045105-creuse'の最適性を示した。
静的記述子とルートレベルの特徴を用いて、ゲートテールアップリフトを持つツリーベースの予測子は、密閉試験分割における平均絶対誤差0.058とスピアマンランク相関0.65を達成する。
特徴重要度分析は, 根の縮退, 行列構造, 係数範囲, プリゾルト還元を高WVSの主要因とする。
可変性は、安価な早期実行機能から体系的で部分的に予測可能であるため、プリエンプティブチューニングのための実用的なツールを提供し、新しいアルゴリズムを公平に評価するための基礎を築いた。
関連論文リスト
- Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking [38.97446792838266]
部分的インフォームド最適化(PISO)は、利用可能なコンポーネントと残余イテレーションの実行推定を組み合わせたものである。
滑らかな非目的に対して、残差の初期等級に依存する収束保証を確立する。
PISOは、リプシッツと(O(d2varepsilon-5)の下で、さらにリプシッツとヘッセンの仮定の下で、主要な関数探索複合体(Od2varepsilon-6)を得る。
論文 参考訳（メタデータ） (2026-10-09T17:20:41Z) - SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming [22.62136761133081]
Mixed-Integer Linear Programming (MILP)は、最適化における基本的な最適化パラダイムであり、現実世界のドメインに広く適用されている。
NPハードの性質のため、大規模または高度に制約されたMILPインスタンスの最適解を求めることは禁じられている。
本稿では,ワンショット方式の並列デコーディングを新しい条件付きデコーディング機構に置き換える構造対応階層型解予測フレームワークを提案する。
論文 参考訳（メタデータ） (2026-08-26T01:41:45Z) - Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
共有トランスブロックを繰り返し適用するLooped Transformerは、可変長の計算タスクに自然に適合するアーキテクチャである。
この差分を、列長とループ数の間の単純なアルゴリズムタスクにおける突発的相関に追従する。
私たちの研究は、"停止する時"は単なる推論時間割当ルールではなく、トレーニング設計の選択として扱われるべきであることを示唆しています。
論文 参考訳（メタデータ） (2026-06-29T08:58:09Z) - Loop-Extrusion Linkage: Spectral Ordering and Interval-Based Structure Discovery for Continuous Optimization [0.0]
本稿では,適応変数インター推定,ファイドラーベクトルによるスペクトルセレーション,適応間隔に基づく部分空間探索を組み合わせた構造学習ラッパーであるLoop-Extrusion(LEL)演算子を紹介する。
特定の構造仮説を変調したd=96の6つの診断関数についてLELを評価した。
結果は、ホルム=ボンフェロニ補正とヴァルガ=デレーニーA12効果の大きさでウィルコクソンのサインランク試験によって評価される。
論文 参考訳（メタデータ） (2026-04-05T21:26:21Z) - Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。
クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。
我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文 参考訳（メタデータ） (2026-02-05T14:16:47Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - Rethinking LLM Evaluation: Can We Evaluate LLMs with 200x Less Data? [82.09573568241724]
EssenceBenchは反復遺伝的アルゴリズム(GA)を利用した粗粒度フレームワーク
提案手法は, 再構成誤差が低く, 効率が著しく向上した, 優れた圧縮結果が得られる。
HellaSwagベンチマーク(10Kサンプル)では,25倍少ないサンプルを用いて,全モデルが5%以内の順位を保ち,わずか200倍少ないサンプルを用いて,95%未満のランキング保持シフトを達成している。
論文 参考訳（メタデータ） (2025-10-12T05:38:10Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - Efficient Semi-Implicit Variational Inference [65.07058307271329]
効率的でスケーラブルな半単純外挿 (SIVI) を提案する。
本手法はSIVIの証拠を低勾配値の厳密な推測にマッピングする。
論文 参考訳（メタデータ） (2021-01-15T11:39:09Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。