論文の概要: Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning

• arxiv url: http://arxiv.org/abs/2207.13701v1
• Date: Tue, 26 Jul 2022 15:34:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-29 12:09:49.833453
• Title: Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning
• Title（参考訳）: オフラインランキングに基づくポリシー学習による効率的な混合整数型プログラミングのための分岐ランキング
• Authors: Zeren Huang, Wenhao Chen, Weinan Zhang, Chuhan Shi, Furui Liu, Hui-Ling Zhen, Mingxuan Yuan, Jianye Hao, Yong Yu, Jun Wang
• Abstract要約: オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
• 参考スコア（独自算出の注目度）: 45.1011106869493
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Deriving a good variable selection strategy in branch-and-bound is essential for the efficiency of modern mixed-integer programming (MIP) solvers. With MIP branching data collected during the previous solution process, learning to branch methods have recently become superior over heuristics. As branch-and-bound is naturally a sequential decision making task, one should learn to optimize the utility of the whole MIP solving process instead of being myopic on each step. In this work, we formulate learning to branch as an offline reinforcement learning (RL) problem, and propose a long-sighted hybrid search scheme to construct the offline MIP dataset, which values the long-term utilities of branching decisions. During the policy training phase, we deploy a ranking-based reward assignment scheme to distinguish the promising samples from the long-term or short-term view, and train the branching model named Branch Ranking via offline policy learning. Experiments on synthetic MIP benchmarks and real-world tasks demonstrate that Branch Rankink is more efficient and robust, and can better generalize to large scales of MIP instances compared to the widely used heuristics and state-of-the-art learning-based branching models.
• Abstract（参考訳）: 分岐とバウンドにおける優れた変数選択戦略の導出は、現代の混合整数計画法(MIP)の効率化に不可欠である。 以前の解法プロセスで収集されたMIP分岐データにより、最近、分岐法への学習はヒューリスティックスよりも優れている。 ブランチ・アンド・バウンドは当然シーケンシャルな意思決定タスクであるので、各ステップを識別する代わりに、mip解決プロセス全体の有用性を最適化する方法を学ぶべきです。 本研究では、オフライン強化学習(RL)問題として分岐学習を定式化し、分岐決定の長期的な有用性を評価するオフラインMIPデータセットを構築するための長期監視型ハイブリッド検索手法を提案する。 ポリシトレーニングフェーズでは,長期的ないし短期的な視点から有望なサンプルを識別するためのランキングベースの報酬割り当てスキームを展開し,オフラインポリシ学習によるブランチランキングと呼ばれるブランチモデルをトレーニングする。 合成MIPベンチマークと実世界のタスクの実験により、ブランチランクはより効率的で堅牢であり、広く使われているヒューリスティックスや最先端の学習ベース分岐モデルと比較して、大規模なMIPインスタンスに最適化できることが示された。

関連論文リスト

• Lifelong Learning for Neural powered Mixed Integer Programming [6.297356207581819]
  混合プログラム(MIP)は、通常ブランチ・アンド・バウンド・アルゴリズムによって解決される。 本稿では,二部グラフの分岐形式でMIPインスタンスをモデル化するアイデアを取り入れたLIMIPを提案する。 我々は,NP-hard問題に対するLIMIPの評価を行い,既存のベースラインと比較すると,生涯学習に直面すると,LIMIPが最大50%向上することが確認された。
  論文  参考訳（メタデータ） (2022-08-24T09:05:40Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
  論文  参考訳（メタデータ） (2022-06-14T16:35:58Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。 MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。 我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
  論文  参考訳（メタデータ） (2022-02-22T05:41:43Z)
• Text Generation with Efficient (Soft) Q-Learning [91.47743595382758]
  強化学習(RL)は、任意のタスクメトリクスを報酬としてプラグインすることで、より柔軟なソリューションを提供する。 ソフトQ-ラーニングの観点からテキスト生成のための新しいRL式を導入する。 雑音/負の例から学習し、敵攻撃、即時生成など、幅広いタスクにアプローチを適用する。
  論文  参考訳（メタデータ） (2021-06-14T18:48:40Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP [2.528056693920671]
  このようなポリシーを2つの設定で学習するオフライン手法を提案する。 1つの設定は、プリンギング中に子供のセレクタに対応し、もう1つはダイビングに似ている。 5つのMIPデータセットの実証結果は、我々のノード選択ポリシーが、文献における最先端の先例よりもはるかに高速な解決につながることを示している。
  論文  参考訳（メタデータ） (2020-07-08T08:12:44Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。 本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2020-02-12T17:43:23Z)

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

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