論文の概要: Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2503.01129v1
• Date: Mon, 03 Mar 2025 03:19:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:16:45.838609
• Title: Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming
• Title（参考訳）: Apollo-MILP: 混合整数線形計画のための交互予測補正ニューラルソルビングフレームワーク
• Authors: Haoyang Liu, Jie Wang, Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye Hao, Feng Wu,
• Abstract要約: Apollo-MILP (Alternating Prediction-correction Neural solve framework) を提案する。 各イテレーションにおいて、Apollo-MILPは未固定変数の予測ステップを実行し、その後修正ステップを行い、信頼領域探索を通じて改善された解(参照解と呼ばれる)を得る。 一般的なベンチマーク実験により,提案したApollo-MILPは,ソリューションの品質の観点から,他のMLベースのアプローチよりも大幅に優れていることが示された。
• 参考スコア（独自算出の注目度）: 57.24050601521162
• License:
• Abstract: Leveraging machine learning (ML) to predict an initial solution for mixed-integer linear programming (MILP) has gained considerable popularity in recent years. These methods predict a solution and fix a subset of variables to reduce the problem dimension. Then, they solve the reduced problem to obtain the final solutions. However, directly fixing variable values can lead to low-quality solutions or even infeasible reduced problems if the predicted solution is not accurate enough. To address this challenge, we propose an Alternating prediction-correction neural solving framework (Apollo-MILP) that can identify and select accurate and reliable predicted values to fix. In each iteration, Apollo-MILP conducts a prediction step for the unfixed variables, followed by a correction step to obtain an improved solution (called reference solution) through a trust-region search. By incorporating the predicted and reference solutions, we introduce a novel Uncertainty-based Error upper BOund (UEBO) to evaluate the uncertainty of the predicted values and fix those with high confidence. A notable feature of Apollo-MILP is the superior ability for problem reduction while preserving optimality, leading to high-quality final solutions. Experiments on commonly used benchmarks demonstrate that our proposed Apollo-MILP significantly outperforms other ML-based approaches in terms of solution quality, achieving over a 50% reduction in the solution gap.
• Abstract（参考訳）: 近年,混合整数線形プログラミング(MILP)の初期解を予測する機械学習(ML)が広く普及している。 これらの手法は解を予測し、変数のサブセットを固定して問題次元を減少させる。 そして、還元された問題を解いて最終解を得る。 しかし、変数値を直接固定することは、予測された解が十分正確でない場合、低品質な解や不可能な還元問題につながる可能性がある。 この課題に対処するために、修正すべき正確で信頼性の高い予測値を識別し、選択できる代替予測補正ニューラルネットワークフレームワーク(Apollo-MILP)を提案する。 各イテレーションにおいて、Apollo-MILPは未固定変数の予測ステップを実行し、その後修正ステップを行い、信頼領域探索を通じて改善された解(参照解と呼ばれる)を得る。 予測および参照解を組み込むことにより、予測値の不確実性を評価し、高い信頼度で修正する、新しい不確実性ベースのエラーアッパーバウンド(UEBO)を導入する。 Apollo-MILP の特筆すべき特徴は、最適性を保ちながら問題削減の優れた能力であり、高品質な最終解をもたらすことである。 一般的なベンチマーク実験により,提案したApollo-MILPは,ソリューション品質の観点から他のMLベースのアプローチよりも有意に優れ,解ギャップの50%以上を達成していることが示された。

関連論文リスト

• RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks [3.3894236476098185]
  混合整数線形プログラミング (MILP) は様々な分野にまたがる最適化手法である。 本稿では,最初の実現可能な解を見つけるだけでなく,より有効な解を段階的に発見する新しい強化学習(RL)に基づく解法を提案する。
  論文  参考訳（メタデータ） (2024-11-29T07:23:34Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
  制約付き最適化のための学習型反復解法を提案する。 解法を特定のパラメトリック最適化問題にカスタマイズすることで、非常に高速で正確な解を得ることができる。 最適性のKarush-Kuhn-Tucker条件に基づく新しい損失関数を導入し、両ニューラルネットワークの完全な自己教師付きトレーニングを可能にする。
  論文  参考訳（メタデータ） (2024-09-12T14:17:23Z)
• V-STaR: Training Verifiers for Self-Taught Reasoners [71.53113558733227]
  V-STaR はモデル生成解の正しさを判断する DPO を用いて検証器を訓練する。 複数のイテレーションでV-STaRを実行すると、徐々により良い推論器と検証器が得られる。
  論文  参考訳（メタデータ） (2024-02-09T15:02:56Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。 我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。 本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
  論文  参考訳（メタデータ） (2023-12-07T15:55:58Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。 本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
  論文  参考訳（メタデータ） (2023-11-12T21:54:53Z)
• OKRidge: Scalable Optimal k-Sparse Ridge Regression [21.17964202317435]
  スパースリッジ回帰のための高速アルゴリズムOKRidgeを提案する。 また,ビームサーチを利用した解法を温める方法を提案する。
  論文  参考訳（メタデータ） (2023-04-13T17:34:44Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Efficient Approximation of Expected Hypervolume Improvement using Gauss-Hermite Quadrature [0.0]
  ガウス・ハーマイト二次構造はモンテカルロの独立性および相関性のある予測密度に対する正確な代替物である。 独立性および相関性のある予測密度に対するモンテカルロの正確な代替であることを示す。
  論文  参考訳（メタデータ） (2022-06-15T22:09:48Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)

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

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