論文の概要: SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2102.09193v1
• Date: Thu, 18 Feb 2021 07:34:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-19 14:32:01.970522
• Title: SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning
• Title（参考訳）: SeaPearl: 強化学習による制約プログラミングソリューション
• Authors: F\'elix Chalumeau (1), Ilan Coulon (1), Quentin Cappart (2), Louis-Martin Rousseau (2) ((1) \'Ecole Polytechnique, Institut Polytechnique de Paris, (2) \'Ecole Polytechnique de Montr\'eal)
• Abstract要約: 本稿では,Juliaで実装された新しい制約プログラミング問題であるSeaPearlの概念実証について述べる。 seapearlは強化学習を使用して分岐決定を学ぶために機械学習ルーチンをサポートする。 産業用ソリューションとはまだ競合していないが、seapearlは柔軟でオープンソースなフレームワークを提供することを目指している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete enumeration of the solution set. A critical and non-trivial design choice with such methods is the branching strategy, directing how the search is performed. The last decade has shown an increasing interest in the design of machine learning-based heuristics to solve combinatorial optimization problems. The goal is to leverage knowledge from historical data to solve similar new instances of a problem. Used alone, such heuristics are only able to provide approximate solutions efficiently, but cannot prove optimality nor bounds on their solution. Recent works have shown that reinforcement learning can be successfully used for driving the search phase of constraint programming (CP) solvers. However, it has also been shown that this hybridization is challenging to build, as standard CP frameworks do not natively include machine learning mechanisms, leading to some sources of inefficiencies. This paper presents the proof of concept for SeaPearl, a new CP solver implemented in Julia, that supports machine learning routines in order to learn branching decisions using reinforcement learning. Support for modeling the learning component is also provided. We illustrate the modeling and solution performance of this new solver on two problems. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework in order to facilitate future research in the hybridization of constraint programming and machine learning.
• Abstract（参考訳）: 組合せ最適化問題を解決するための効率的で汎用的なアルゴリズムの設計は長年にわたって活発に研究されてきた。 標準的な正確な解法は、ソリューションセットの巧妙で完全な列挙に基づいています。 このような方法による重要かつ自明でない設計の選択は分岐戦略であり、検索の実行方法を指示する。 過去10年間、組合せ最適化問題を解決するために機械学習ベースのヒューリスティックスの設計に関心が高まっている。 目標は、過去のデータからの知識を活用して、同様の新しい問題の事例を解決することだ。 単独で使うと、そのようなヒューリスティックスは近似解を効率的に提供できるだけであるが、解の最適性や境界を証明できない。 近年の研究では、強化学習が制約プログラミング(CP)ソルバの探索フェーズの駆動に有効であることが示されている。 しかし、標準CPフレームワークには機械学習メカニズムがネイティブに含まれていないため、このハイブリッド化は構築が難しいことも示されています。 本論文では、強化学習を用いた分岐決定を学習するために機械学習ルーチンをサポートするJuliaで実装された新しいCPソルバであるSeaPearlのコンセプト実証について述べる。 学習コンポーネントのモデリングもサポートされている。 この新しいソルバーのモデリングとソリューションのパフォーマンスを2つの問題で説明します。 SeaPearlは、産業用ソルバーとはまだ競合していないが、制約プログラミングと機械学習のハイブリッド化における将来の研究を促進するために、柔軟でオープンソースのフレームワークを提供することを目指している。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。 本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。 本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
  論文  参考訳（メタデータ） (2024-01-11T15:02:15Z)
• Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT [4.873362301533824]
  車両ルーティングはNPハード最適化問題のよく知られたクラスである。 最近の強化学習の取り組みは有望な代替手段である。 本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-14T06:27:09Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。 このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
  論文  参考訳（メタデータ） (2022-03-04T17:06:00Z)
• End-to-End Constrained Optimization Learning: A Survey [69.22203885491534]
  機械学習アーキテクチャとソルバと最適化手法を統合する作業の調査に焦点を当てている。 これらのアプローチは、問題に対する迅速、近似、構造的、解決策を予測し、論理的推論を可能にする新しいハイブリッド機械学習と最適化手法を開発することを約束します。
  論文  参考訳（メタデータ） (2021-03-30T14:19:30Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization [5.669790037378094]
  目標は、有限個の可能性の集合の中で最適解を見つけることである。 深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。 制約プログラミング(CP)は最適化問題を解決する汎用ツールである。 本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
  論文  参考訳（メタデータ） (2020-06-02T13:54:27Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。 強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
  論文  参考訳（メタデータ） (2020-03-07T16:19:45Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。 本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
  論文  参考訳（メタデータ） (2020-01-03T11:01:52Z)

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

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