論文の概要: Learning Early-to-Final Solution Consistency for MILP Acceleration

• arxiv url: http://arxiv.org/abs/2608.19953v1
• Date: Thu, 20 Aug 2026 12:18:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-21 20:28:51.560509
• Title: Learning Early-to-Final Solution Consistency for MILP Acceleration
• Title（参考訳）: MILP高速化のための早期から最適解の整合性学習
• Abstract要約: Mixed-Integer Linear Programming (MILP)は、オペレーションの研究と最適化における基本的な問題クラスである。 最近の学習ベースアプローチは、静的なインスタンスレベルの特徴から高品質なソリューションを直接予測することで、MILP解決を加速させようとしている。 そこで本稿では,学習対象を変数代入から早期から最終整合にシフトする,新たな解法インフォームドパラダイムを提案する。
• 参考スコア（独自算出の注目度）: 23.616127937763896
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.
• Abstract（参考訳）: Mixed-Integer Linear Programming (MILP) は、業務研究と組合せ最適化における基本的な問題クラスであり、工業的意思決定に広く応用されている。 しかし、NP硬度のため、現代の解法は実用的な時間制限内でMILPインスタンスに挑戦するための高品質な解を見つけるのに苦労する可能性がある。 最近の学習ベースアプローチは、変数制約二部グラフのような静的なインスタンスレベルの特徴から、高品質なソリューションを直接予測することで、MILP解決を加速しようとしている。 インスタンスの特徴だけでは正確な解の予測は困難であり、これらの手法は解の探索過程において明らかにされた情報を概ね見落としている。 本稿では,MILPソルバの初期探索段階で生成した解が,計算的に安価に入手でき,フル予算探索後に得られる解と構造的に近い場合が多いことを明らかにする。 そこで本研究では,学習対象を変数代入から早期から最終的整合性へシフトする,新たな解法インフォームド・パラダイムを提案する。 予測された一貫性は、例えば一貫したと見なされる割り当てを修正することによって、下流の探索を自然に導く。 推論時には、ロバスト性を改善するために、複数の初期段階のソリューション間で整合性予測をさらにアンサンブルする。 4つのMILPベンチマークによる実験により,提案手法は下流パイプライン間の予測誘導探索を改善した。 Gurobi では,提案手法により一次間隙を平均で56.9%減らし,組合せオークションで完全に閉鎖する。 また,グロビ訓練モデルゼロショットを適応せずにSCIPに移行し,ベンチマークの平均ギャップを36.4%削減した。

関連論文リスト

• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
  本稿では,混合整数最適化問題の事例を大まかに解くための,学習に基づく新しい手法を提案する。 提案手法は,混合整数最適化問題の離散成分を学習するグラフベース生成拡散モデルに依存する。 Constrained Graph Diffusion (CGD) という名前のフレームワークは問題に依存しず、様々な混合整数最適化問題に対応できる。
  論文  参考訳（メタデータ） (2026-08-13T10:46:18Z)
• 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)
• Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming [57.24050601521162]
  Apollo-MILP (Alternating Prediction-correction Neural solve framework) を提案する。 各イテレーションにおいて、Apollo-MILPは未固定変数の予測ステップを実行し、その後修正ステップを行い、信頼領域探索を通じて改善された解(参照解と呼ばれる)を得る。 一般的なベンチマーク実験により,提案したApollo-MILPは,ソリューションの品質の観点から,他のMLベースのアプローチよりも大幅に優れていることが示された。
  論文  参考訳（メタデータ） (2025-03-03T03:19:49Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。 提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
  論文  参考訳（メタデータ） (2023-12-26T03:09:08Z)
• Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs [5.28005598366543]
  ニューラルダイビング(ND)は、混合プログラム(MIP)における部分的な離散変数代入を生成する学習ベースのアプローチの1つである。 カバー範囲を最適化するためのポストホック法と学習に基づくアプローチを導入する。 実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。
  論文  参考訳（メタデータ） (2023-08-01T07:03:16Z)
• Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning [4.521119623956821]
  混合整数線形二段階プログラムの解を高速化する手法を提案する。 我々は,第2段階の要求の高い問題を解決することを目的としている。 私たちの中核となる考え方は、オンラインソリューションの時間を大幅に削減し、第一段階ソリューションの精度を小さくすることです。
  論文  参考訳（メタデータ） (2022-05-02T13:15:32Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。 すべての予測と最適化アプローチのボトルネックに対処する。 非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T19:09:12Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Sequential Transfer in Reinforcement Learning with a Generative Model [48.40219742217783]
  本稿では,従来の課題から知識を移譲することで,新たな課題を学習する際のサンプルの複雑さを軽減する方法について述べる。 この種の事前知識を使用することのメリットを明確に示すために,PAC境界のサンプル複雑性を導出する。 簡単なシミュレートされた領域における理論的な発見を実証的に検証する。
  論文  参考訳（メタデータ） (2020-07-01T19:53:35Z)

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

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