論文の概要: SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2608.25282v1
• Date: Wed, 26 Aug 2026 01:41:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-27 14:15:15.526732
• Title: SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming
• Title（参考訳）: SHSP:混合整数線形計画のための構造を考慮した階層的解予測
• Abstract要約: Mixed-Integer Linear Programming (MILP)は、最適化における基本的な最適化パラダイムであり、現実世界のドメインに広く適用されている。 NPハードの性質のため、大規模または高度に制約されたMILPインスタンスの最適解を求めることは禁じられている。 本稿では,ワンショット方式の並列デコーディングを新しい条件付きデコーディング機構に置き換える構造対応階層型解予測フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 22.62136761133081
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignment for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods, and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.
• Abstract（参考訳）: Mixed-Integer Linear Programming (MILP) は組合せ最適化の基本的な最適化パラダイムであり、現実世界のドメインに広く適用されている。 NPハードの性質のため、大規模または高度に制約されたMILPインスタンスに対する最適解を求めることは、計算的に禁じられている。 したがって、学習に基づく解予測は、解法加速のための高品質な変数割り当てを提供するための有望なアプローチとして現れてきた。 しかし、既存の手法では、全ての変数の限界確率を同時に予測するワンショット予測パラダイムを採用するのが一般的である。 その結果、変数間の条件依存はメッセージパッシングによってのみ暗黙的にキャプチャされ、グラフニューラルネットワークの表現能力に完全に依存する組合せ構造をモデル化する責任がある。 この制限に対処するために,1ショットメソッドの並列境界復号を新しい階層型条件付き復号機構に置き換える構造対応階層型解予測(SHSP)フレームワークを提案する。 具体的には、SHSPは制約構造から変数結合グラフを構築し、結合強度を増大させる階層に沿って変数を逐次デコードする。 復号処理中のエラーの蓄積を軽減するため、SHSPはさらに信頼性に配慮したマスク・アンド・リペア機構を導入し、信頼性の低い中間予測を識別し修正する。 SHSPを複数の学習誘導探索手法と統合し、4つの標準MILPベンチマークで評価する。 実験の結果,SHSPは既存の一発予測ベースラインを著しく上回り,解のギャップを平均54%減少させることがわかった。

関連論文リスト

• A Unified Framework for Gradient Aggregation in Multi-Objective Optimization [23.311857116714176]
  我々はMOOにおける勾配集約のための統一フレームワークを開発する。 両錐体への射影により実現可能性を保証することを示し、収束保証を許容する手法の範囲を広げる。 本稿では、確立されたアルゴリズムを包含し、それらの理論的関係を明確化し、新しい変種の設計を可能にする勾配集約の最適化的視点を示す。
  論文  参考訳（メタデータ） (2026-05-28T18:21:53Z)
• Barrier-enforced multi-objective optimization for direct point and sharp interval forecasting [1.0966260566122237]
  本稿では,単一ニューラルネットワークモデルを用いた多段階確率予測フレームワークを提案する。 我々のアプローチは、ターゲットカバレッジ確率(PICP)を厳密に満たしたモデル構造設計により、非交差予測間隔(PI)を保証する。 その結果, 提案した損失は, PI幅が最も狭い対象範囲を達成し, 現行文献よりも一貫して優れていた。
  論文  参考訳（メタデータ） (2026-04-20T16:43:12Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。 本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。 本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
  論文  参考訳（メタデータ） (2026-02-10T14:17:53Z)
• Multiscale Aggregated Hierarchical Attention (MAHA): A Game Theoretic and Optimization Driven Approach to Efficient Contextual Modeling in Large Language Models [0.0]
  マルチスケール集約階層的注意(MAHA)は、階層的分解と数学的に厳密な集約を通じて注意機構を再構築する新しいアーキテクチャフレームワークである。 MAHAは、入力シーケンスを学習可能なダウンサンプリング演算子を介して階層スケールに動的に分割する。 実験的なFLOP解析により,4096のシークエンス長で計算コストが81%削減されたことが確認された。
  論文  参考訳（メタデータ） (2025-12-16T21:27:21Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  シンボルレベルのプリコーディングにおいて,推論の複雑さの低いエンドツーエンドディープラーニング(DL)フレームワークを提案する。 提案手法は,従来の手法よりも約80倍の高速化を実現しつつ,SLPの大幅な性能向上を達成できることを示す。
  論文  参考訳（メタデータ） (2025-10-02T15:15:50Z)
• Neural Optimal Transport Meets Multivariate Conformal Prediction [58.43397908730771]
  条件付きベクトル回帰(CVQR)のためのフレームワークを提案する。 CVQRは、ニューラルネットワークの最適輸送と量子化された最適化を組み合わせて、予測に適用する。
  論文  参考訳（メタデータ） (2025-09-29T19:50:19Z)
• FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
  Mixed-Integer Linear Programming (MILP)は、複雑な意思決定問題の基本的なツールである。 混合整数線形計画法(FMIP)のための連立連続整数フローを提案する。これはMILPソリューションにおける整数変数と連続変数の共分散をモデル化する最初の生成フレームワークである。 FMIPは任意のバックボーンネットワークや様々なダウンストリームソルバと完全に互換性があり、現実世界のMILPアプリケーションにも適している。
  論文  参考訳（メタデータ） (2025-07-31T10:03:30Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
  論文  参考訳（メタデータ） (2024-07-24T12:00:30Z)
• Conditional Mean and Variance Estimation via \textit{k}-NN Algorithm with Automated Variance Selection [9.943131787772323]
  条件平均と分散度を共同で推定するための新しいテクストリック・アレスト・ニアレスト回帰法(textitk-NN)を提案する。 提案アルゴリズムは,古典的非パラメトリックテクトitk-NNモデルの計算効率と多様体学習能力を保持する。
  論文  参考訳（メタデータ） (2024-02-02T18:54:18Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。 本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
  論文  参考訳（メタデータ） (2023-11-12T21:54:53Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Efficient differentiable quadratic programming layers: an ADMM approach [0.0]
  乗算器の交互方向法(ADMM)に基づく代替ネットワーク層アーキテクチャを提案する。 後方微分は、修正された固定点反復の残差写像の暗黙の微分によって行われる。 シミュレーションの結果は、中規模の問題に対してOptNet二次プログラミング層よりも約1桁高速であるADMM層の計算上の利点を示している。
  論文  参考訳（メタデータ） (2021-12-14T15:25:07Z)

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

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