論文の概要: Learning Primal Heuristics for Mixed Integer Programs

• arxiv url: http://arxiv.org/abs/2107.00866v1
• Date: Fri, 2 Jul 2021 06:46:23 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-06 01:09:40.527374
• Title: Learning Primal Heuristics for Mixed Integer Programs
• Title（参考訳）: 混合整数プログラムの原始的ヒューリスティックス学習
• Authors: Yunzhuang Shen, Yuan Sun, Andrew Eberhard, Xiaodong Li
• Abstract要約: 本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。 本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。 可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
• 参考スコア（独自算出の注目度）: 5.766851255770718
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes a novel primal heuristic for Mixed Integer Programs, by employing machine learning techniques. Mixed Integer Programming is a general technique for formulating combinatorial optimization problems. Inside a solver, primal heuristics play a critical role in finding good feasible solutions that enable one to tighten the duality gap from the outset of the Branch-and-Bound algorithm (B&B), greatly improving its performance by pruning the B&B tree aggressively. In this paper, we investigate whether effective primal heuristics can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Convolutional Network on solved problem instances with known optimal solutions. This in turn can predict the values of decision variables in the optimal solution for an unseen problem instance of a similar type. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search (PB-DFS) approach, aiming to find (near-)optimal solutions quickly. The experimental results show that this new heuristic can find better primal solutions at a much earlier stage of the solving process, compared to other state-of-the-art primal heuristics.
• Abstract（参考訳）: 本稿では,機械学習技術を用いた混合整数プログラムのための新しい原始ヒューリスティックを提案する。 混合整数プログラミングは組合せ最適化問題を定式化する一般的な手法である。 解法の内部では、分岐境界アルゴリズム(B&B)の開始から双対性ギャップを狭め、B&B木を積極的に刈り取ることでその性能を大幅に向上させる、優れた実現可能な解を見つける上で、原始ヒューリスティックスが重要な役割を果たす。 本稿では,機械学習を用いて有効原始ヒューリスティックスを自動学習できるかどうかを検討する。 本稿では,最適化問題をグラフとして表現する新しい手法を提案し,既知の最適解を持つ解問題インスタンス上でグラフ畳み込みネットワークを訓練する。 これにより、類似型の未解決問題インスタンスの最適解における決定変数の値を予測することができる。 可変解の予測は,B&B法(PB-DFS)を用いた確率分岐法(Probabilistic Branching with guided Depth-first Search, PB-DFS)の新たな構成により,(ほぼ)最適解の探索を迅速に行う。 実験の結果、この新しいヒューリスティックは、他の最先端の原始ヒューリスティックと比較して、解法プロセスのずっと早い段階でより優れた原始解を見出すことができた。

関連論文リスト

• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2024-09-07T19:52:14Z)
• Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization [59.386153202037086]
  Predict-Then-フレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 このアプローチは非効率であり、最適化ステップを通じてバックプロパゲーションのための手作りの、問題固有のルールを必要とする。 本稿では,予測モデルを用いて観測可能な特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2023-11-22T01:32:06Z)
• Taking the human out of decomposition-based optimization via artificial intelligence: Part I. Learning when to decompose [0.0]
  本稿では,モノリシックな解法か分解型解法かを自動的に判定するグラフ分類手法を提案する。 学習した分類器を既存の構造的混合整数最適化解法に組み込む方法を示す。
  論文  参考訳（メタデータ） (2023-10-10T23:31:06Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• End-to-End Constrained Optimization Learning: A Survey [69.22203885491534]
  機械学習アーキテクチャとソルバと最適化手法を統合する作業の調査に焦点を当てている。 これらのアプローチは、問題に対する迅速、近似、構造的、解決策を予測し、論理的推論を可能にする新しいハイブリッド機械学習と最適化手法を開発することを約束します。
  論文  参考訳（メタデータ） (2021-03-30T14:19:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• First-Order Methods for Convex Optimization [2.578242050187029]
  一階法は、計算量が少なくて精度の低い解を提供する可能性がある。 我々は、様々な重要な結果の完全な証明を行い、いくつかの最適化アルゴリズムの統一的な側面を強調した。
  論文  参考訳（メタデータ） (2021-01-04T13:03:38Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。 すべての予測と最適化アプローチのボトルネックに対処する。 非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T19:09:12Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。 高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
  論文  参考訳（メタデータ） (2020-04-14T14:11:00Z)

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

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